代码随想录算法训练营：23/60

非科班学习算法day23 | LeetCode39:组合总和，Leetcode40:组合总和||

介绍

包含LC的两道题目，还有相应概念的补充。

1.LeetCode39:组合总和

题目链接：39. 组合总和 - 力扣（LeetCode）

题目解析

明确问题需求，组合：没有顺序要求，可以有重复；总和：中止条件，剪枝条件。

这里和之前题目最大的区别就是可以重复，也就是说可以从头开始，所以注意递归的参数是i

还有一个问题就是需不需要index，实际上是需要的，因为index可以帮助我们取寻找在一个数组中当前寻找元素的位置，比如说，一开始找的是0位，进入递归，下一层还是会从0开始选取；下一个for里面i已经++了，所以进入到1位的分支，以上这句话也可以增加对回溯的理解。

c++代码如下：

class Solution {
public:
    // 路径
    vector<int> path;
    // 结果
    vector<vector<int>> res;
    // 回溯函数-重复选取
    void backtracking(vector<int>& candidates, int target, int index, int sum) {
        if (sum > target)
            return;
        // 中止,收集结果
        if (sum == target) {
            res.push_back(path);
            return;
        }

        for (int i = index; i < candidates.size(); i++) {
            path.push_back(candidates[i]);
            sum += candidates[i];
            backtracking(candidates, target, i, sum);
            path.pop_back();
            sum -= candidates[i];
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtracking(candidates, target, 0, 0);
        return res;
    }
};

2.Leetcode40:组合总和||

题目链接：40. 组合总和 II - 力扣（LeetCode）

题目解析

这里有一个和前面不同的区别就是数组中有重复的数字，结果res里面的路径之间要求不可以相同，比如[1,1,1]没有问题，但是res里有两个[1,1,1]就不可以了。

明确了这个需求我们可以根据抽象的树状图分析出来，递归过程其实并没有影响，因为检索过程没有变，但是如果想去重就要把在树层上下功夫。这里没有采用used辅助，可以想象一下，什么能造成重复，前提是将数组排序，如果相邻两个数是一样的，因为我们for是从左到右遍历，那么后面的数构成的结果一定包含在前面的数里。

C++代码如下：

class Solution {
public:
    // 路径
    vector<int> path;
    // 结果
    vector<vector<int>> res;
    // 回溯函数-有重复数字且同一位不可重复选取
    void backtracking(vector<int>& candidates, int target, int sum, int index) {
        if (sum > target)
            return;
        // 收集结果
        if (sum == target) {
            res.push_back(path);
            return;
        }

        for (int i = index; i < candidates.size(); ++i) {
            if (i > index && candidates[i] == candidates[i - 1])
                continue;
            path.push_back(candidates[i]);
            sum += candidates[i];
            backtracking(candidates, target, sum, i + 1);
            path.pop_back();
            sum -= candidates[i];
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0);
        return res;
    }
};

注意点：其他地方都没有问题，只需要注意去重大多数是要重新排序的，除非说有序返回！