Leetcode39：组合总和——回溯算法

组合总和
问题形貌：给一个组合元素聚集【2 5 3】，都是正整数且没有重复，有一个targer数8， 聚集内里的元素可以重复选，让我们从组合里挑数，使得求和后等于8，返回能求和的组合 ， 答案应该是：【 【2，2，2，2】， 【2,3,3】 ， 【3,5】 】
画树形布局的注意点：
1、路径取了2后，剩余元素仍旧是2 3 5，因为元素可以重复取。
2、第2条分支，取5，剩余元素要从5后开始算，即5 3， 不能有2，因为如果5 2 那么就和前面的2 5重复了。
3、叶子结点判定是否等于target，如果等于，记录这个答案，返回。如果大于target，已经超了，直接返回。如果小于，继承树深查找。

用代码 实现
和组合问题比较大的差别是：选了一个元素后，剩余元素里，要把已经选过的元素带上，这样才能达到重复选取目地。
其他方面和组合问题差不多，只不过是用一个组合的和target，限定树的高度。
回溯三部曲实现：
1、函数返回值 一样平常是void
2、确定停止条件
3、单层搜索逻辑

1. vector<vector<int>> result;
2. vector<int> path;
4. sum判断path路上的和是否等于target。
5. int sum;   
6. startIndex 作用：在第2个分支如何知道从下一个位置开始找，是for循环变量的开始位置。
7. void backtracking(candidate, target, sum, startIndex){
8.     if(sum > taeget) return;
9.     if(sum == target){
10.         result.push_back(path);
11.         return;
12.     }
13.     //单层搜索逻辑,for循环里面的i控制左右,即for的i控制分支，  里面的递归控制高度
14.     for(int i = startIndex; i<candidate.size();i++){
15.         path.push_back(candidate[i]);
16.         sum += candidate[i];
17.         backtracing(candidate, target, sum, i);
18.         //回溯不能掉，如何收集信息，就如何吐出去。
19.         sum -= candidate[i];
20.         path.pop_back();
21.     }
22.     return;
23. }

复制代码

这里附上我的完整的解题代码

1. class Solution {
2. public:
4.     vector<vector<int>> result;
5.     vector<int> path;
6.     int sum=0;
7.     int startIndex=0;
9.     void backtracking(vector<int>& candidates, int target, int sum, int startIndex){
10.         if(sum > target)    return;
11.         if(sum == target){
12.             result.push_back(path);
13.             return;
14.         }
15.         //单层搜索逻辑
16.         for(int i=startIndex; i<candidates.size(); i++){
17.             path.push_back(candidates[i]);
18.             sum += candidates[i];
19.             backtracking(candidates, target, sum, i);
20.             //回溯，撤销删除
21.             sum -= candidates[i];
22.             path.pop_back();
23.         }
24.         return;
25.     }
26.     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
27.         backtracking(candidates, target, 0, 0);
28.         return result;
29.     }
30. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。