预备知识: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 }
原文:https://www.cnblogs.com/fx1998/p/12761517.html