leetcode77. 组合
题目大意
作者：大腿壮
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
解题思路类似于全排列，首先生成长度为n的数组nums，元素为1~n，然后采用回溯法找到所有满足条件的数组。
在回溯中用一维数组curNums记录每个可能的组合。当数组长度等于k时，表明满足条件，将其放入res中并返回。
否则的话，将当前位置至最后位置上的值依次放入curNums中并对该元素位置后面的元素进行回溯。
class Solution {
public:
vector<vector> combine(int n, int k) {
if (n == 0 || k == 0)
return {};
//创建一个{1,2,3,...n}的数组，方便用来回溯
vector nums(n, 0);
for (int i = 0; i < n; ++i)
nums[i] = i + 1;
vector<vector> res;
vector curNums;
dfs(res, nums, curNums, k, 0);
return res;
}
void dfs(vector<vector> & res, vector & nums, vector & curNums, int k, int index){
//若curNums长度满足条件了，则将其放入res中，并结束本次递归
if (curNums.size() == k){
res.push_back(curNums);
return ;
}
if (index == nums.size())
return ;
//依次将index~nums.size()位置的元素放入curNums中，并对其后面的元素进行回溯
for(int i = index; i < nums.size(); ++i){
curNums.push_back(nums[i]);
dfs(res, nums, curNums, k, i + 1);
curNums.pop_back();
}
}
};
作者：大腿壮
