排列数字——DFS

问题描述

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10;

int path[N];	// 记录排列顺序
bool st[N];		// 当前下标表示的数字是否已经加入排列顺序中了
int n;

void dfs(int u)	// u表示当前位置
{
	if(u == n)	// 所有数字都排列完成
	{
		for(int i = 0;i < n; i++) cout << path[i] << " ";
		puts("");
		return;
	}
	for(int i = 1; i <= n; i++)	// 遍历所有数字，找到没有加入排列顺序中的数字
	{
		if(!st[i])
		{
			st[i] = true;
			path[u] = i;
			dfs(u + 1);	// 判断下一个位置
			st[i] = false;	// 回溯
		}
	}
}

int main()
{
	cin >> n;
	dfs(0);
}