[力扣leetcode39]组合总和及回溯法

• 回溯yyds
• 小练习

回溯yyds

在算法优化上面回溯法或许没有那么引人注意，但是对于一些题目来说能够回溯已经很好了。

题目：给定一个无重复元素的数组 candidates 和一个目标数 target ，找candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。
比如输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]

对于这道题目最朴素的解法当然是暴力搜索，但是其实组合类问题一直都是回溯法的天下，可以排除一些没有必要的验证。回溯法的本质我个人认为是一个树，不妨以上述的输入为例。

第一轮2，3，6，7都可以选，如果第一轮选了2，第二轮可以选2，3，因为必须要满足每一轮取的数必须大于等于上一轮取的数，这样可以避免重复，同时不需要取6，7，因为要满足总和为7。如果第二轮取了2，第三轮可以取2，3，先验证2，不满足且不能继续取了，回溯上一轮再取3，发现满足题意，即找到一个组合。所以思路就来了，用for循环遍历元素，再用回溯法。回溯法有个明显的格式是进栈（或者其他容器）->回溯->出栈。需要额外注意的是startindex的选取，本题每一轮选取的数都要大于等于上一轮的数。

class Solution { private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {if (sum > target) {return;}if (sum == target) {result.push_back(path);return;}for (int i = startIndex; i < candidates.size(); i++) {sum += candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, sum, i); sum -= candidates[i];path.pop_back();}} public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {result.clear();path.clear();backtracking(candidates, target, 0, 0);return result;} };

小练习

因为上学期离散学到了球和盒子的问题，比较难的是把不可辨别的球放到不可辨别的盒子里面，典型的就是自然数的组合问题，比如3，可以有1+1+1，1+2，两种组合方式。这个问题也可以用回溯法解决。

vector<vector<int>> res; vector<int> vec; void back(int n,int cur){int sum=accumulate(vec.begin(),vec.end(),0);if(sum==n){res.push_back(vec);return;}for(int i=cur;i<n;i++){if(i+sum<=n)vec.push_back(i);else return;back(n,i);vec.pop_back();}}int main(){int n=6;back(n,1);for(int i=0;i<res.size();i++){for(int j=0;j<res[i].size();j++){cout<<res[i][j];}cout<<endl;} }

总结

以上是生活随笔为你收集整理的[力扣leetcode39]组合总和及回溯法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。