94. 递归实现排列型枚举

题目：

94. 递归实现排列型枚举 - AcWing题库 

 

思路： 

1.全排列问题（坑位问题）---->递归搜索树---->用dfs深度优先搜索。

2. u表示当前坑位，state[u]表示坑位u存储的数据。因为不同坑位的数据不可以重复，故引入used[i]用于判断数据i是否使用过。

3.注意恢复现场。

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
const int N = 10;
int state[N];//0表示还没有放数，1~n表示放了哪个数
using namespace std;
bool used[N];//true表示用过，false表示没有
int n;
void dfs(int u)
{if (u > n)//越界{for (int i = 1; i <= n; i++)printf("%d ", state[i]);puts("");//换行return;}//依次枚举每一个分支，即当前位置可以填哪些数for (int i = 1; i <= n; i++) if (!used[i]) {state[u] = i;used[i] = true;dfs(u+1);//恢复现场state[u] = 0;used[i] = false;}
}
int main()
{scanf("%d", &n);dfs(1);return 0;
}