代码随想录算法训练营第24天 | 理论基础、77. 组合

77. 组合 - 力扣（LeetCode）

思路:

• 使用回溯法，将每一次递归都当成一次循环，递归传入参数为结果数组，临时数组(用来存储单次k个数的组合)，k,n以及cntn(用来表示本次递归加入tmp数组的数字)。递归终止条件是tmp.size() == k，即此时tmp数组中已有k个数组，可以加入结果数组。递归每一层的处理逻辑是一个循环，循环的工作是将该层所有要遍历的元素都加入tmp数组中，然后进行下一层递归，此时要进行回溯

减枝操作：

• 递归中的循环若剩余的数字不足k - tmp.size()个则结束循环，即循环进行条件设置为i <= n - (k - tmp.size()) + 1

我的AC代码

class Solution {
public:
    void backtracking(vector<vector<int>>& ans, vector<int>& tmp, int cntn, int k, int n) {
        if(tmp.size() == k) {
            ans.push_back(tmp);
            return;
        }
        for(int i = cntn; i <= n - (k - tmp.size()) + 1; ++i) {
            tmp.push_back(i);
            backtracking(ans, tmp, i + 1, k, n);
            tmp.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ans;
        vector<int> tmp;
        backtracking(ans, tmp, 1, k, n);
        return ans;
    }
};

标准答案

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) { // 优化的地方
            path.push_back(i); // 处理节点
            backtracking(n, k, i + 1);
            path.pop_back(); // 回溯，撤销处理的节点
        }
    }
public:

    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }
};