AcWing 递归实现排列型枚举 dfs

AcWing 递归实现排列型枚举 dfs

AcWing 递归实现排列型枚举 dfs

预备知识:1~n这n个数的全排列共有2^n种。
  证明:第一个位置有n种情况,第二个位置有(n-1)种情况,最后一个位置有1种情况,
n * (n - 1) * ... * 1 = n!
搜索顺序:从前往后遍历每个位置,判断这个位置放哪个数。
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n;
 4 const int N = 10;
 5 int st[N]; //0表示还没放数,1~n表示放了哪个数 
 6 bool used[N]; //判断每个数有没有被用过,true表示用过,false没用过 
 7 void dfs(int u) {
 8     if (u == n + 1) {
 9         for (int i = 1; i <= n; i++) { //打印方案 
10             cout << st[i] << " ";
11         }
12         cout << endl;
13         return; 
14     }
15     //依次枚举每个分支,即当前位置可以放哪些数
16      for (int i = 1; i <= n; i++) { //从小到大 
17          if (!used[i]) { //找一个没用过的数 
18             st[u] = i; //放在u这个位置 
19             used[i] = true; //i这个数用过了
20             dfs(u + 1); //搜索下一层 
21             st[u] = 0; //回溯回复现场 
22             used[i] = false;
23          }
24      }
25 }
26 int main() {
27     cin >> n;
28     dfs(1); //从第一位开始 
29     return 0;
30 } 

AcWing 递归实现排列型枚举 dfs

上一篇:教你用PS把课本上的图表处理成纯黑白图表


下一篇:.Net - WebApi