虚拟网站官网,学做网站论坛vip视频,廊坊智能模板建站,郑州专业网站制作费用报价题目#xff1a;
94. 递归实现排列型枚举 - AcWing题库 思路#xff1a;
1.全排列问题#xff08;坑位问题#xff09;----递归搜索树----用dfs深度优先搜索。
2. u表示当前坑位#xff0c;state[u]表示坑位u存储的数据。因为不同坑位的数据不可以重复#…题目
94. 递归实现排列型枚举 - AcWing题库 思路
1.全排列问题坑位问题----递归搜索树----用dfs深度优先搜索。
2. u表示当前坑位state[u]表示坑位u存储的数据。因为不同坑位的数据不可以重复故引入used[i]用于判断数据i是否使用过。
3.注意恢复现场。
代码
#includecstdio
#includeiostream
#includealgorithm
#includecstring
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(u1);//恢复现场state[u] 0;used[i] false;}
}
int main()
{scanf(%d, n);dfs(1);return 0;
}
