LeetCode 77.组合

博主 851 2020-09-12

给定两个整数 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);
    }
};