Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:
[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
思路:这是一道组合题,组合的个数为C(n,k)。可用递归将其打印出来,例如C(5,2),用used数组表示1...n是否已被用,a数组表示每一种组合情况。在打印每一种组合情况时,可知右侧的数组均大于左侧数字。因此程序如下:
class Solution { private: vector<vector<int> >aa; vector<int> a; public: void combineHelper(int n,int k,int pos,int *used,int leftMin) { if(pos == k) { aa.push_back(a); } else { int i; for(i=1; i<=n; ++i) { if(used[i] == 0 && i > leftMin) { a[pos] = i; used[i] = 1; combineHelper(n,k,pos+1,used, i); used[i] = 0; } } } } vector<vector<int> > combine(int n, int k) { int used[n+1]; memset(used,0,sizeof(used)); //0表示未使用,1表示已使用 aa.clear(); a.clear(); a.resize(k); if(n==0 || k==0) { return aa; } combineHelper(n,k,0,used,0); return aa; } };