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

leetcode39-组合总和

时间:2022-09-24 18:22:23浏览次数:74  
标签:target 组合 int sum vector candidates leetcode39 size 总和

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

相关文章

  • 组合总和 II
    组合总和II题目介绍给定一个候选人编号的集合candidates和一个目标数target,找出candidates中所有可以使数字和为target的组合。candidates中的每个数字在每......
  • 组合日记-九月二十三日
    成立条件\(\displaystyle\sum_{k}{\binom{n}{k}\binom{s}{k}k},n\in\mathbb{N}\)有点像LINK的\(1.\)式。\(\displaystyle\mathrm{Lemma1}:\binom{n}{k}=\binom{......
  • leetcode17-电话号码的字母组合
    17.电话号码的字母组合这题还是看了题解才写出来。一开始不懂得每一层递归处理不同数字对应的字母,又想一些二维数组的操作,就搞复杂了。题中的index就代表当前正在处理......
  • windows server 2012 中怎么进行NIC组合
    NIC组合就是把同一台服务器上的多个物理网卡通过软件绑定成一个虚拟的网卡,也就是说,对于外部网络而言,这台服务器只有一个可见的网卡。对于任何应用程序,以及本服务器所在的网......
  • leetcode216-组合总和 III
    216.组合总和III 有了 77.组合 的启发后,就成功地自己写了通过的代码classSolution{public:vector<vector<int>>res;vector<int>path;ints......
  • leetcode77-组合
    77.组合classSolution{public:vector<vector<int>>res;vector<int>path;voidbackTracking(intn,intk,intstartIndex){if(path.......
  • 组合日记-九月二十二日
    循环节的推导\(\displaystyleQ_n=\sum_{k\le2^n}{\binom{2^n-k}{k}}(-1)^k,n\in\mathbb{N^+}\)试求\(Q_{1000000}\)。观察到\(n\)只以\(2^n\)的形式出现过,设......
  • P2822 [NOIP2016 提高组] 组合数问题
    P2822[NOIP2016提高组]组合数问题题解作者岛田小雅这是一道复杂度非常容易爆炸的问题。我看到这题的第一眼,第一反应是直接按照公式暴力跑。我们看一眼数据范围。如......
  • R语言学习丨数据重塑、拆分与组合基础知识,merge、melt、cast函数介绍
    今天学习R语言中数据重塑相关基础知识,主要有merge、melt、cast函数用法示例。公众号:生信分析笔记合并数据框merge()函数能够以一列为参考合并两个不同数据框,相当于数学中......
  • 巧用自动化测试组合拳保证产品质量
    https://mp.weixin.qq.com/s/oFTqhwN2Oy1zYP2vszsY2g“如何保证质量”一直是产品或项目过程中关注的焦点,而测试是产品质量把控环节中非常关键的部分。本文结合我们的实践......