给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/combinations
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
一道组合型枚举题
假设我们要找到一个长度为n的所有子序列ai,1~n的每个数字都有选择和不选两种情况,一共是2^n个子序列。
本题目要求我们从n个数字选k个数字作为子序列,则在选择子序列数字的时候需要当选取的数字个数为k个时,提前返回,得到该子序列。
要注意递归的边界条件:当待选择的数字num从1递增到n+1时,到达边界。
在本题中可以进行提前剪枝,假设当前已经选择了q个数字,后面还有w个数字供选择,而当q+w < k时,既即使选择完后续所有w个数字,也不能凑成k个数字的子序列,可以进行提前返回。
在下面的代码中,没有判断递归的边界条件,因为num不可能到达n+1:
在q+w < k时剪枝,在q+w >= k时,在到达k时就得到了子序列,并返回。于是可以去掉判断递归边界的代码。
代码:
class Solution {
private:
vector<vector<int> > ans;
vector<int> temp;
int n;
int k;
public:
// 给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。
vector<vector<int> > combine(int n, int k) {
this->n = n;
this->k = k;
dfs(1);
return ans;
}
void dfs(int pos){
// 剪枝: 即使加上从pos~n的所有数字 都不能达到k个数字 直接返回
if (temp.size() + (n-pos+1) < k) {
return;
}
if (temp.size() == k) { // 记录答案
ans.push_back(temp);
return;
}
// 选择当前数字
temp.push_back(pos);
dfs(pos+1);
temp.pop_back();
// 不选择当前数字
dfs(pos+1);
}
};
Comments | 2 条评论