组合

题目

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

思路

同时使用循环和递归，每个循环负责一层的数据遍历，递归一次就进入下一层（也就是k个数的第二个），直至k=0

class Solution {
public:
    vector<vector<int>> res;
    void combineAux(vector<int>& tmp, int n, int k)
    {
        for(int i=n;i>=k;--i)
        {
            tmp[k-1] = i;
            if(k-1 == 0)
            {
                res.emplace_back(tmp);
                continue;
            }
            combineAux(tmp, i-1, k-1);
        }
    }
    vector<vector<int>> combine(int n, int k) {
        vector<int> vec(k);
        combineAux(vec, n, k);
        return res;
    }
};

剪枝优化

可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。

如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。