39. 组合总和
首先是原始的错误代码
class Solution { public: int size,sum=0; vector<vector<int>> res; vector<int> path; void backTracking(vector<int>& candidates, int target,int startNum) { if(sum==target) { res.push_back(path);return; } if(sum>target) return; for(int i=startNum;i<size-1&&(candidates[i]+sum<=target);i++) { sum+=candidates[i];path.push_back(candidates[i]); backTracking(candidates,target,startNum);//这里应该传入i,一开始没有留意到这里是错的,导致有【2,2,3】,【2,3,2】【3,2,2】这样的结果 sum-=candidates[i];path.pop_back(); sum+=candidates[i+1];path.push_back(candidates[i+1]); backTracking(candidates,target,i+1);//实际上并不需要这三行代码,因为for循环已经帮我们重复加上同一个数然后加下一个数的处理了。这三行会导致出现几个一模一样的中间结果 sum-=candidates[i+1];path.pop_back(); } } vector<vector<int>> combinationSum(vector<int>& candidates, int target) { size=candidates.size(); sort(candidates.begin(),candidates.end()); backTracking(candidates,target,0); return res; } };
看了卡尔的代码,其实和我原始的代码没什么差别,我这里还剪了枝
这是修改后的
class Solution { public: int size,sum=0; vector<vector<int>> res; vector<int> path; void backTracking(vector<int>& candidates, int target,int startNum) { if(sum==target) { res.push_back(path);return; } if(sum>target) return; for(int i=startNum;i<size;i++) { if(candidates[i]+sum>target) break; sum+=candidates[i];path.push_back(candidates[i]); backTracking(candidates,target,i);//应该传入i sum-=candidates[i];path.pop_back(); } } vector<vector<int>> combinationSum(vector<int>& candidates, int target) { size=candidates.size(); sort(candidates.begin(),candidates.end()); backTracking(candidates,target,0); return res; } };
标签:target,组合,int,sum,vector,candidates,leetcode39,size,总和 From: https://www.cnblogs.com/uacs2024/p/16726163.html