当前位置：首页 > article >正文

数组总和（leetcode 40

article 2025/3/13 17:31:35

leetcode系列

文章目录

一、核心操作
二、外层配合操作
三、核心模式代码
总结

去重方式和之前三数之和一样，也可以用used数组去重，但本次尝试使用set去重

一、核心操作

如果count为0了，则证明正好减到了0，就可以收获，并返回
建立unordered_set
开始循环，如果在set中能够搜寻到当前的数字，说明已经重复了，则直接进行下一次的循环，如果没有找到，则说明这是一个没有重复的新数字，将其加入set中，后面则直接进行常规操作

提示：小白个人理解，如有错误敬请谅解！

二、外层配合操作

对数组进行排序

三、核心模式代码

代码如下：

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backTracking(vector<int>& candi, int count, int startIndex)
    {
        if(count==0)
        {
            res.push_back(path);
            return;
        }
        unordered_set<int> uset;
        for(int i=startIndex;i<candi.size()&&(count-candi[i])>=0;i++)
        {
            if(uset.find(candi[i])!=uset.end())continue;
            uset.insert(candi[i]);
            path.push_back(candi[i]);
            backTracking(candi,count-candi[i],i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        if(!candidates.size())return res;
        sort(candidates.begin(),candidates.end());
        backTracking(candidates,target,0);
        return res;
    }
};