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

发布于 2022-12-09  267 次阅读


AI 摘要

本文讲解了 LeetCode 上的第 77 题组合的解题思路。使用回溯法解题,每次递归当成一次循环,若 tmp 数组已经有 k 个数,则可以加入结果数组。递归中的循环长度根据剩余数字数量进行减枝。同时,给出了作者的 AC 代码和标准答案的代码以供参考。

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;
    }
};