组合总和

前言

在上篇文章通过组合问题看透回溯法当中咱们通过介绍一个组合问题，认真地剖析了组合问题的回溯过程。咱们之后会持续介绍一些比拟经典的回溯算法题，帮忙深刻彻底了解回溯算法的执行过程和原理，如果对回溯的整个过程还不是很理解的话能够先浏览下面那篇文章。

组合总和

给你一个 无反复元素 的整数数组 candidates 和一个指标整数 target ，找出 candidates 中能够使数字和为指标数 target 的 所有 不同组合 ，并以列表模式返回。你能够按 任意程序 返回这些组合。

candidates 中的 同一个 数字能够 无限度反复被选取 。如果至多一个数字的被选数量不同，则两种组合是不同的。

对于给定的输出，保障和为 target 的不同组合数少于 150 个。

例1：

输出：candidates = [2,3,6,7], target = 7输入：[[2,2,3],[7]]解释：2 和 3 能够造成一组候选，2 + 2 + 3 = 7 。留神 2 能够应用屡次。7 也是一个候选， 7 = 7 。仅有这两种组合。

例2：

输出: candidates = [2,3,5], target = 8输入: [[2,2,2,2],[2,3,3],[3,5]]

解法

依据题目的意思咱们是须要从给定的汇合当中选出几个数据，而且能够进行反复选取，只须要保障被咱们选中的数据的和为target即可。对于这个问题咱们能够结构一个如下图所示的解树：（上面的树的target = 8, candidates = [2,3,5]，当被选中的数据的和大于8的时候咱们不须要再往下进行遍历了，因为再抉择数据的话，被抉择的数据的和只会大于8，这永远不可能等于target = 8）

可能你会对下面的解树有所疑难，为什么咱们选完2之后是从[2, 3, 5]当中持续抉择数据，抉择完3之后是从[3,5]当中持续抉择数据，而抉择完5之后只能从[5]当中抉择数据呢？

事实上咱们是须要穷举所有的组合的而后一一进行匹配，所以咱们当初的问题是下面的树穷举完所有的组合了吗？下面的树是穷举完所有的组合了的，上面咱们剖析一下为什么下面的树可能笼罩所有的组合。

穷举的组合如下：

  • 第一个数据和其余所有数据进行组合，
  • 第二个数据和其余所有数据的组合。
  • 第三个数据和其余所有数据的组合。
  • ....

咱们当初来仔细分析一样下面的解树：

  • 咱们再进行第一次抉择的时候，当咱们抉择完2之后还能够从[2, 3, 5]当中进行抉择，这就示意了2和其余所有数据[3, 5]进行了组合，因为题目阐明咱们还能够进行反复抉择，因而还退出了2，这就保障了2进行了所有的组合。
  • 咱们再进行第一次抉择的时候。当咱们抉择3的时候，还能从[3, 5]当中进行抉择，抉择3的起因也是因为能够反复进行抉择，然而抉择5的起因是因为须要和其余所有数据进行组合。在这里你可能还会有一个疑难就是3不是只和5进行了组合吗，还缺它和2的组合啊，认真想一想咱们在前一步抉择2的时候曾经将2和3的组合遍历过一遍了，因而在这不须要再进行组合了。
  • 同样的情理咱们在第一次抉择5的时候，不须要和在他后面的数据进行组合，因为在他后面的数据曾经遍历过所有跟5的组合了。

写代码的流程

  • 仔细分析程序递归的过程，剖析求解问题的树，失去代码的主题思路，依据剖析的后果咱们能够设计咱们函数会有哪些参数，在这道题目当中咱们须要记录选中的数据的汇合的和，这样就能够防止重复去计算选中数据的和了，还有以后遍历到数据的下标。
backtrace(vector<int> &candidates, int target, int idx, int curSum)

  • 确定递归函数的进口：

    • 在这里咱们一个进口就是，当被选中的汇合当中的数据的和满足要求的时候就进行退出。
    • 当被选中的数据的和大于给定的值的时候咱们不须要再进行遍历了，因为即便遍历失去的后果应用会大于给定的值，因而没有遍历的必要了，下图当中深红色的节点就是示意和大于给定的值的状况。

if(curSum == target) {    ans.push_back(path);}if(curSum >= target || idx >= candidates.size())    return;

  • 依据咱们思路确定咱们函数的主体局部：

    for (int i = idx; i < candidates.size(); ++i) {    path.push_back(candidates[i]);    curSum += candidates[i];    backtrace(candidates, target, i, curSum);    path.pop_back();    curSum -= candidates[i];}

残缺代码

C++版

class Solution {    vector<vector<int>> ans;    vector<int> path;public:    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {        backtrace(candidates, target, 0, 0);        return ans;    }    void backtrace(vector<int> &candidates, int target, int idx, int curSum) {        if(curSum == target) {            ans.push_back(path);        }        if(curSum >= target || idx >= candidates.size())            return;        for (int i = idx; i < candidates.size(); ++i) {            path.push_back(candidates[i]);            curSum += candidates[i];            backtrace(candidates, target, i, curSum);            path.pop_back();            curSum -= candidates[i];        }    }};

Java版

class Solution {    private List<List<Integer>> res = new ArrayList<>();    private List<Integer> path = new ArrayList<>();    public List<List<Integer>> combinationSum(int[] candidates, int target) {        solve(candidates, target, 0, 0);        return res;    }    public void solve(int[] candidates, int target, int startPosition,                      int curSum) {        if (curSum == target) {            res.add(new ArrayList<>(path));            return;        }        else if (curSum > target) return;        for (int i = startPosition; i < candidates.length; i++) {            path.add(candidates[i]);            curSum += candidates[i];            solve(candidates, target, i, curSum);            path.remove(path.size() - 1);            curSum -= candidates[i];        }    }}

总结

这道题目体现了经典的回溯过程，就是在往汇合当退出数据之后，再通过遍历实现，就须要将之前退出的数据移出，而这个回到开始的状态的景象就叫做回溯，即回到之前的状态。然而在这个题目当中还须要留神一点的是他的数据能够反复进行应用，因而在遍历传递参数的时候须要传递的是i而不是i+1，这一点须要留神。

以上就是本篇文章的所有内容了，我是LeHung，咱们下期再见！！！更多精彩内容合集可拜访我的项目：https://github.com/Chang-LeHu...

关注公众号：一无是处的钻研僧，理解更多计算机（Java、Python、计算机系统根底、算法与数据结构）常识。