全排列问题

1.3.1 全排列问题
Description

输出自然数 11 到 nn 所有不重复的排列，即 nn 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

Input
第一行为一个整数n

Output
由1至n组成的所有不重复的数字序列，每行一个序列。

每个数字之间由空格隔开

Sample Input

3
Sample Output

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Hint

1≤n≤9

#include<iostream>
using namespace std;
bool visit[10];//搜索时的记录数组
int n;//n的全排列
int line[10];//答案数组，总比所排列的数多1，以后深度搜索的时候越界
void print()//打印函数
{
	for (int i = 1;i <= n;i++)
	{
		cout << line[i]<<" ";
	}
	cout << endl;
}
void DFS(int x)
{
	if (x == n + 1)
		print();//深度搜索的结束条件：当答案数组的x=n+1时，至于为什么为n+1看后续步骤
	else
	{
		for (int i = 1;i <= n;i++)//每次调用深度搜索的时候从答案数组的1开始找没被搜索到的数
		{
			if (!visit[i])//如果没被标记则执行
			{
				visit[i] = 1;//标记为1
				line[x] = i;//答案数组将这个数记录
			    DFS(x+1);
				visit[i] = 0;//重新标记为0以便回溯的时候再次搜索
			}
		}
	}
}
int main()
{
	cin >> n;
	DFS(1);//从1开始搜索，所以每次搜索的时候都为顺序排列
}