1.指数型枚举：1~n里选任意个的所有情况：
通过数组记录每个数字的选择情况：未决定，选，不选
对没选过的数，可以直接选或者不选，所以往选和不选两个方向递归
递归参数是当前要做选择的数
void dfs(int x){ if(x > n){ for(int i = 1;i <= n;i++){ if(f[i] == 2) cout << i << " "; } puts(""); return; } f[x] = 2; dfs(x+1); // f[x] = 0; f[x] = 1; dfs(x+1); // f[x] = 0; }
2.组合型枚举
1~n里·选m个的所有情况
bool数组记录选择情况
没选过就选
//通过保证递增来保证枚举的情况不和之前的情况重复
递归参数写当前在选第几个数
void dfs(int x){ if (x + n - (f[x-1]+1) < m) return; // 剪枝：凑不齐m个数了 if(x > m){ for(int i = 1;i <= m;i++){ cout << f[i] << " "; } puts(""); return ; } for(int i = f[x-1]+1;i <= n;i++){//通过保证递增来保证枚举的情况不和之前的情况重复 if(!st[i]){ f[x] = i; st[i] = true; dfs(x+1); f[x] = 0; st[i] = false; } } }
3.排列型枚举
bool数组记录选不选当前情况，递归时没选过就直接选
递归不用保证递增
void dfs(int x){ //dfs到达边界 if(x > n){ for(int i = 1;i <= n;i++){ cout << f[i] << " "; } puts(" "); return; } //dfs 开始枚举分支 for(int i = 1;i <= n;i++){ if(!st[i]){ st[i] = true; f[x] = i; dfs(x+1); st[i] = false; // f[i] = 0;dfs的回溯流程，但在代码层面无实际意义 } } }
