利用深度优先搜索的性质可以方便的生成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 !!!\n"); 8 return; 9 } 10 if(cnt == num){ 11 for(int i = 0;i < cnt;i ++) printf("%d ",tmp[i]); 12 printf("\n"); 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!!!\n"); 8 return; 9 } 10 if(cnt == k){ 11 for(int i = 0;i < cnt;i ++) printf("%d ",tmp[i]); 12 printf("\n"); 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 }
原文：http://www.cnblogs.com/anhuizhiye/p/3684967.html