combinations(组合数)

https://www.nowcoder.com/practice/4d0a110416d84c7f9454d0da53ab2da1?tpId=46&tqId=29101&tPage=4&rp=4&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking

搜索回溯即可.不过注意为了防止重复出现,比如3 个数字选2个数字。避免出现1 3 和3 1 这种结果，在选数的时候都是从前面已选好的数字的下一位开始选。

class Solution { public: vector<vector<int> > combine(int n, int k) { vector<vector<int> >res; if(n <= 0 || k <= 0) return res; vector<bool>mark(n+1);//标记数字是否被用过 vector<int>temp; dfs(0, n, k, 0, mark, temp, res); return res; } //pos表示上次选的数字的位置，n,k是n个数字，选k个数字 void dfs(int pos, int n, int k, int now, vector<bool> & mark, vector<int> &temp, vector<vector<int> > & res ){ if(now == k){//选足够k个数字 res.push_back (temp); return ; } if(n - pos < k - now)//剪枝。剩下的数字不够（k-now）个了 return; //从下一个位置选择。避免出现1 3 和 3 1 这种重复的情况 for(int i = pos + 1; i <= n; i++){ if(!mark[i] ){//数字i没有选过 mark[i] = true; temp.push_back (i);//选进去 now++;//已选的数目增加 int tmp_pos = i; dfs(tmp_pos, n, k, now, mark, temp, res); //回溯 mark[i] = false; temp.pop_back(); now--; } } } };