dfs 生成排列和组合

利用深度优先搜索的性质可以方便的生成n的排列和组合，但是生成组合时每个组合里面元素的个数必须事先确定，以前以为生成组合跟排列一样到n时就可以回溯，直到今天做了某题之后才发现那是错的，那样做生成不了所有的组合。

生成排列（默认是全排列，也可以传个参数生成n的k排列）

 1 #include<cstdio>
 2 #define MAXN 111
 3 using namespace std;
 4 int tmp[MAXN],vis[MAXN],n,k;
 5 void dfs(int cnt,int num = n){
 6     if(num > n){
 7         printf("the input data is invalid !!!
");
 8         return;
 9     }
10     if(cnt == num){
11         for(int i = 0;i < cnt;i ++) printf("%d ",tmp[i]);
12         printf("
");
13     }
14     for(int i = 1;i <= n;i ++){
15         if(!vis[i]){
16             vis[i] = 1;
17             tmp[cnt] = i;
18             dfs(cnt+1,num);
19             vis[i] = 0;
20         }
21     }
22 }
23 int main(){
24     while(~scanf("%d%d",&n,&k)) dfs(0,k);
25     return 0;
26 }

生成组合

 1 #include<cstdio>
 2 #define MAXN 111
 3 using namespace std;
 4 int tmp[MAXN],n,k;
 5 void dfs(int idx,int cnt,int k){
 6     if(k > n){
 7         printf("the input data is invalid!!!
");
 8         return;
 9     }
10     if(cnt == k){
11         for(int i = 0;i < cnt;i ++) printf("%d ",tmp[i]);
12         printf("
");
13     }
14     for(int i = idx;i <= n;i ++){
15             tmp[cnt] = i;
16             dfs(i+1,cnt+1,k);
17     }
18 }
19 int main(){
20     while(~scanf("%d%d",&n,&k)) dfs(1,0,k);
21     return 0;
22 }