LeetCode39. 组合总和

题目

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。

  • 所有数字(包括 target)都是正整数。
  • 解集不能包含重复的组合。

分析

此题和 77题组合题目类似,又有区别。同一个数字可以无限制底被选取,意味着搜索的深度可能不确定,但是我们可以限制搜索的深度,即递归的终止条件是当前总和大于target。

题目又要求解集不存在重复组合,并且一个数可重复选取,那么每次递归时 startIndex就不必为 i 加一,直接为 i 。

LeetCode39. 组合总和

代码

 1 class Solution {
 2 public:
 3     vector<int>path;
 4     vector<vector<int>> res;
 5     void backtracking(const vector<int>& candidates,int target,int sum,int startIndex){
 6         if(sum > target){
 7             return;
 8         }
 9         if(sum == target){
10             res.push_back(path);
11             return;
12         }
13         for(int i = startIndex;i < candidates.size();i++){
14             sum += candidates[i];
15             path.push_back(candidates[i]);
16             backtracking(candidates,target,sum,i);
17             sum -= candidates[i];
18             path.pop_back();
19         }
20     } 
21     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
22         backtracking(candidates,target,0,0);
23         return res;
24     }
25 };

再进行剪枝优化

上面代码可知,我们是在 sum > target 时,结束递归,实际上在上一次递归尾部就可进行预判,也就是不用进入这层递归,即如果知道下层递归 sum > target 那么就没有必要进入下一层递归了。

如何进行修改呢 ?我们可以增强进入 for 循环的条件,因为只要进入了 for 循环,就会进入下一层递归。对总集合排序之后,如果下一层的sum(就是本层的 sum + candidates[i])已经大于target,就可以结束本轮for循环的遍历

    for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) 

LeetCode39. 组合总和

 

 

 1 class Solution {
 2 public:
 3     vector<int>path;
 4     vector<vector<int>> res;
 5     void backtracking(const vector<int>& candidates,int target,int sum,int startIndex){
 6         if(sum > target){
 7             return;
 8         }
 9         if(sum == target){
10             res.push_back(path);
11             return;
12         }
13         for(int i = startIndex;i < candidates.size() && sum + candidates[i] <= target;i++){
14             sum += candidates[i];
15             path.push_back(candidates[i]);
16             backtracking(candidates,target,sum,i);
17             sum -= candidates[i];
18             path.pop_back();
19         }
20     } 
21     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
22         sort(candidates.begin(),candidates.end());
23         backtracking(candidates,target,0,0);
24         return res;
25     }
26 };

一定要先进行排序,再去回溯

 

上一篇:umijs开启dva-immer


下一篇:2021.3.15刷题-组合总和(元素可重复选取)