823. 排列

823. 排列 823. 排列

给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入格式

共一行，包含一个整数 n。

输出格式

按字典序输出所有排列方案，每个方案占一行。

数据范围

1≤n≤9

输入样例：

3

输出样例：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

//dfs深度优先
//从第一层开始按层往下递归搜索 

#include

using namespace std;

int n;

void dfs(int c, int a[], int b[])//c存当前层数
{
	if (c > n)
	{
		for (int i = 1; i <= n; i ++) cout << a[i] << ' ';//按层填的从1开始输出
		cout << endl;
	}
	else
	{
		for (int i = 1; i <= n; i ++)
		{
			if (b[i] == 0)
			{
			    a[c] = i;
    			b[i] = 1;
    			dfs(c + 1, a, b);
    			b[i] = 0;//恢复现场，下一情况就是轮到用i+1填第c层了，没用i 
			}
			
		}
	}
}


int main()
{
	cin >> n;
	
	int a[10], b[10] = {0};//a存数值，b存数值使用情况,10个位置存9个数
	dfs(1, a, b); 
	
	
	
	return 0;	
}