40. 组合总和 II
这题和 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; } 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+1); sum-=candidates[i]; path.pop_back(); while(i<=size-2&&candidates[i+1]==candidates[i]) i++; } } vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(),candidates.end()); size=candidates.size(); backTracking(candidates,target,0); return res; } };
如果没有for循环最后的while语句,结果将会变成这样
为什么这个判断语句不能在进入递归之前使用?如上图所示,重复的元素是可以放到一起的,while放到递归前就会少了几个包含重复元素的中间结果。
while循环放到递归之后就是为了,此轮循环结束后的下一个值为另一个值不相同的值。
标签:target,int,sum,II,while,candidates,path,leetcode40,总和 From: https://www.cnblogs.com/uacs2024/p/16726300.html