首页 > 其他分享 >leetcode40-组合总和 II

leetcode40-组合总和 II

时间:2022-09-24 19:24:45浏览次数:67  
标签:target int sum II while candidates path leetcode40 总和

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

相关文章