在递归中可以画出一个递归树,再由递归树找出退出条件和每次递归的做法
递归实现指数型枚举
例:枚举1~n的任取m个数的各种排列,0 =< m =< n,1 =< n <= 15.
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 16;
int n;
int ways[N]; //0表示未使用,1表示有这个数字, 2表示没有这个数字
void dfs(int u){
if(u > n){
for(int i = 1; i <= n; i++){
if(ways[i] == 1)
printf("%d ", i);
}
puts("");
return;
}
ways[u] = 1;
dfs(u+1);
ways[u] = 0;
ways[u] = 2;
dfs(u+1);
ways[u] = 0;
}
int main()
{
scanf("%d", &n);
dfs(1);
return 0;
}
递归的排列型枚举
例:将1~n进行全排列,1 =< n <= 9.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 10;
int n;
int ways[N];
bool used[N]; //需要判断是否用过某个数
void dfs(int u){
if(u > n){
for(int i = 1; i <= n; i++){
printf("%d ", ways[i]);
}
puts("");
return;
}
for(int i = 1; i <= n; i++){
if(!used[i] == true){
used[i] = true;
ways[u] = i;
dfs(u+1);
used[i] = false;
}
}
}
int main(){
scanf("%d", &n);
dfs(1);
return 0;
}