声明：本算法参考了网上其它的一些算法，在此表示感谢，由于是时隔很久的一个总结，相关参考链接已经忘了，故此处没有给出参考页面，敬请见谅~~~
组合问题：
问题：
给定两个数n和r，求出从1到n中选出r个数的组合
例如 n=5, r=3
结果：1,2,3 1,2,4 1,2,5 1,3,4 1,3,5 1,4,5 2,3,4 2,3,5 3,4,5
注意：
如果你需要对一个数组的内容进行组合，你可以先对数组下标进行组合，然后再根据下标转换成对应的内容，故本算法具有通用性。
1.采用回溯法实现
分析：
主要有两个回溯点，最外层的回溯点 a[i]=n时需要回溯
其它层回溯点 a[i] > i + r 当前数组值a[i]肯定是小于索引i+ r
例如上例：a[0] 1~3 a[1] 2~4 a[2] 3~5 规律a[i] i+1~ i + r
#include <iostream> using namespace std; /* * 组合问题 */ const int MAXSIZE = 20; int a[MAXSIZE]; /* * 采用回溯法实现 */ void Comb(int n, int r) { int pos = 0; a[0] = 1; while(a[0] <= n-r+1) { if(pos < r-1) { if(a[pos] <= pos + r)//是否需要回溯 { a[pos+1] = a[pos] + 1; pos++; } else //回溯 { pos--; a[pos] = a[pos] + 1; } } else if(pos == r-1) { for(int i=0; i<r; i++) { cout << a[i] << " "; } cout << endl; if(a[pos] == n)//是否需要回溯 { pos--; a[pos]++; } else { a[pos] = a[pos] + 1; } } } } int main() { Comb1(5, 3, 3); system("pause"); return 0; }
2.递归方式实现
我们知道a[r-1] n-r+1 ~ n,对于comb(n,r),假设已经选取了a[r-1],剩余的问题就是comb(n-1, r-1),可以使用递归来实现
/* * 采用递归实现 */ void Comb1(int n, int r, int r1)//r1保存r的最初取值，便于后面输出 { for(int i=n; i>=r; i--) { a[r-1] = i; if(r > 1) { Comb1(i-1, r-1, r1); } else { for(int j=r1-1; j>=0; j--) { cout << a[j] << " "; } cout << endl; } } } int main() { Comb1(5, 3, 3); system("pause"); return 0; }
