LeetCode 77.组合

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