代码随想录算法训练营第二十四天|77.组合、216.组合Ⅲ

文档链接：https://programmercarl.com/

LeetCode77.组合

题目链接：https://leetcode.cn/problems/combinations/

思路：

回溯三部曲：

第一步：确定函数返回值和参数类型

第二步：确定终止条件

第三步：确定单层递归逻辑

那么这一题for循环用来横向遍历集合中的元素（也就是n），递归用来纵向遍历树的深度（也就是k），这么说很绕，先尽量理解这吧。至于为什么参数要引入一个startIndex，为了不重复遍历数据。

回溯：

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(int n, int k, int startIndex) {
        if(path.size() == k) {
            result.push_back(path);
            return ;
        }
        for(int i = startIndex; i <= n; i++) {
            path.push_back(i);
            backtracking(n, k, i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }
};

剪枝优化：

接下来看一下优化过程如下：

1. 已经选择的元素个数：path.size();

2. 还需要的元素个数为: k - path.size();

3. 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。

举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。

从2开始搜索都是合理的，可以是组合[2, 3, 4]。

这里大家想不懂的话，建议也举一个例子，就知道是不是要+1了。

所以优化之后的for循环是：

for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置

LeetCode216.组合Ⅲ

题目链接：https://leetcode.cn/problems/combination-sum-iii/

思路：同组合一样

回溯（记录一下自己写出来的）：

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(int k, int n, int startIndex) {
        if(path.size() == k && n == 0) {
            result.push_back(path);
            return;
            
        }
        for(int i = startIndex; i <= 9; i++) {
            path.push_back(i);
            backtracking(k, n - i, i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(k, n, 1);
        return result;
    }
};

剪枝优化：

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(int k, int n, int startIndex) {
        if(n < 0) return ;
        if(path.size() == k && n == 0) {
            result.push_back(path);
            return;
            
        }
        for(int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
            path.push_back(i);
            backtracking(k, n - i, i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(k, n, 1);
        return result;
    }
};

总结：算法课学过回溯，但是仅限于纸上谈兵，现在好后悔当初浪费的时光，到那时回头想想那是也不是说在闲着，只不过一直忙忙碌碌，一直碌碌无为罢了，现在在看回溯，既熟悉又陌生，尽快捡起来吧。