LeetCode #39. 组合总和

LeetCode #39. 组合总和

I. Description：II. Solution：Version 1解题思路：Code: Version 2解题思路：Code:

I. Description：

II. Solution：

Version 1

解题思路：

  该题采用回溯算法的思路进行分析。回溯算法的思路在于：通过枚举法，对所有的可能情况进行遍历。不过枚举的顺序是一条路走到黑，走到走无可走的时候，往前退一步，再尝试之前没走过的下一条路，重复这个过程直到所有的路都走过了。解决回溯问题，实际上就是一个决策树的遍历过程。回溯的实现，主要是依靠$for$循环和递归的结合。回溯法的关键就是：

一条路走到黑走无可走时回退一步

  $for$循环可以给出当前节点下的，所有可以往下走的分支路径；递归意味着继续沿着$for$循环给出的某个路径向下走一步。如果将递归放到$for$循环内部，那么for每一次的循环都在给出一个路径之后，进入递归，也就继续往下走了，直到走无可走为止。这样也就实现了一条路走到黑，当递归达到递归出口(走无可走)时，就会实现往前回退一步。回溯算法的模板就是：

res = [] def backtrack(路径，选择列表): if 满足递归结束条件: res.append(路径) return for 选择 in 选择列表: 做出选择 backtrack(路径，选择列表) 撤销选择

这里的核心就是$for$循环里面的递归，在递归调用前对下一个可能的节点做出选择，递归调用后取消这个选择，进入下一个循环接着作下一个未走过的选择。从上边模板可以总结出，要完成回溯算法的决策树的遍历过程，只需要考虑三个方面：

路径：你已经做出的选择选择列表：当前节点下剩余的可以作出的选择结束条件：也就是到走无可走时的递归跳出的出口

Code:

cpp #include <algorithm> /*Note: 组合不强调元素顺序，排列是强调顺序的*/ class Solution { public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); backtrack(candidates, target, 0, 0); return res; } private: vector<vector<int>> res; // 存放最后的结果 vector<int> Path; //用于存放当前作出的选择 void backtrack(vector<int> &nums, int target, int currentSum, int startIndex) { //结束条件，也就是递归的出口 if(currentSum > target){ return; } if(currentSum == target){ res.push_back(Path); return; } //因为求的是组合，这里i每次是从startIndex开始；若求的的是排列，则i每次从0开始 for (int i = startIndex; i < nums.size(); i++) { Path.push_back(nums[i]); currentSum += nums[i]; backtrack(nums, target, currentSum, i); //这里送入的开始索引位置为i,表示可以重复选取当前的选择 Path.pop_back(); currentSum -= nums[i]; } } };

Version 2

解题思路：

  上面解法中递归函数中的参数可以稍微优化一下，其中的 int $target$, int $currentSum$ 这两个参数的用途就是为了判断递归跳出的结束条件用的，因此可以考虑直接取二者的差值，合并为一个int $diff$参数。

Code:

cpp class Solution { public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); backtrack(candidates, target, 0); return res; } //第二个参数为target与当前已作出选择的总和之间的差值,即diff = target - currentSum //这个参数的目的是用来判断递归结束条件的 void backtrack(vector<int> &nums, int diff, int startIndex) { if (diff < 0) return; if(diff == 0) { res.push_back(Path); return; } for (int i = startIndex; i < nums.size(); i++) { Path.push_back(nums[i]); backtrack(nums, diff - nums[i], i); Path.pop_back(); } } private: vector<vector<int>> res; vector<int> Path; };