40. 组合总和 II

这篇具有很好参考价值的文章主要介绍了40. 组合总和 II。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意:解集不能包含重复的组合。 

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

1、利用startindex进行去重

class Solution {
public:
    vector<vector<int>>res;
    vector<int>path;
    int sum = 0;
    void backtracking(vector<int>& candidates, int target,int startindex){
        if(sum > target) return;
        if(sum == target){
            res.push_back(path);
            return;
        }
        for(int i = startindex;i < candidates.size();i++){
            //1 1 2
            //去重逻辑,就是排序后的木匾数组,在树层遍历(横向遍历)时前一个不能和后一个相等。
            //前一个比后一个的1早,且范围大,第二个1往后遍历的结果,都是第一个1遍历后的子集,即,第一个1早就遍历过了。第二个1再遍历,就会产生重复组合。
            if(i > startindex && candidates[i] == candidates[i-1]){
                //i > startindex,说明当前是在遍历一个树层,横向遍历,startindex不变,i++。
                //i==startindex,说明在一层中选中一个值以后,往下遍历,这一层的i不变,index++.
                continue;
            } 
            else{
                path.push_back(candidates[i]);
                sum += candidates[i];
                backtracking(candidates,target,i+1);
                path.pop_back();
                sum -= candidates[i];
            }
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        //组合不能重复,但是如果有多个位置的元素值相同,则组合内元素值可以相同
        sort(candidates.begin(),candidates.end());
        backtracking(candidates,target,0);
        return res;
    }
};

 2、利用used数组,标记。

引入两个名词->两个维度上的去重

1、树枝去重:比如(1,1,2),向下递归的时候,如果开始用第二个1,发现第一个1用过了,就continue了,会漏掉112,这个结果(题目不允许重复使用一个位置上的相同元素) used[i - 1] == true,说明同一树枝candidates[i - 1]使用过
2、树层去重:(1,1,2),想右遍历的时候,如果遍历到第二个1,发现第一个1使用过(但是used是false,是由于递归回溯的时候,又初始化了),又因为是排过序的,所以第二个1之后遍历到的结果,肯定已经被第一个1包含了,即再取就重复了。 used[i - 1] == false,说明同一树层candidates[i - 1]使用过文章来源地址https://www.toymoban.com/news/detail-726462.html

class Solution {
public:
    vector<vector<int>>res;
    vector<int>path;
    //unordered_map<vector<int>,int>map;
    int sum = 0;
    void backtracking(vector<int>& candidates, int target,int startindex,vector<bool>& used){
        //终止条件
        if(sum > target) return;
        if(sum == target){
            //最开始想用map或者set去重,但是错误不断
            //sort(path.begin(),path.end());
            //map[path]++;
            //if(map[path] > 1) return;// 出现了两次
            //else res.push_back(path);
            res.push_back(path);
            return;
        }
        for(int i = startindex;i < candidates.size();i++){
            //去重
            if(i>0 && candidates[i] == candidates[i-1] && !used[candidates[i-1]]){
                continue;
            }
            path.push_back(candidates[i]);
            sum += candidates[i];
            used[candidates[i]] = true;
            backtracking(candidates,target,i+1,used);
            path.pop_back();
            sum -= candidates[i];
            used[candidates[i]] = false;
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        //为了去重,得排序
        sort(candidates.begin(),candidates.end());
        vector<bool>used(candidates.size(),false);
        backtracking(candidates,target,0,used);

        return res;
    }
};

到了这里,关于40. 组合总和 II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣:40. 组合总和 II

    回溯: 1.先声明好大集合和小集合,在调用回溯函数,终止条件为sum==target,要进行剪枝操作减少遍历的次数,去重操作防止数组中有两个相同的值来组成的集合相同。

    2024年02月21日
    浏览(35)
  • 40. 组合总和 II

    给定一个候选人编号的集合  candidates  和一个目标数  target  ,找出  candidates  中所有可以使数字和为  target  的组合。 candidates  中的每个数字在每个组合中只能使用  一次  。 注意: 解集不能包含重复的组合。  示例 1: 示例 2: 提示: 1 = candidates.length = 100 1 = candidat

    2024年02月07日
    浏览(46)
  • day27 | 39. 组合总和、 40.组合总和II、131.分割回文串

    目录: 39. 组合总和 给你一个  无重复元素  的整数数组  candidates  和一个目标整数  target  ,找出  candidates  中可以使数字和为目标数  target  的 所有 ** 不同组合  ,并以列表形式返回。你可以按  任意顺序  返回这些组合。 candidates  中的  同一个  数字可以  无限

    2024年02月10日
    浏览(42)
  • leetcode动态规划(零钱兑换II、组合总和 Ⅳ)

    给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 示例 1: 输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 示例 2: 输入: amount = 3, coins = [2] 输出: 0 解释: 只用面

    2024年02月01日
    浏览(43)
  • 算法刷题Day 27 组合总和+组合总和II+分割回文子串

    本题的特点是元素为可重复选取的 其实只要在原来的基础上添加一点小小的变化就是实现重复选取(与排列区别开),一时没想出来 这里与39.组合总和 (opens new window)最大的不同就是要去重了。 前面我们提到:要去重的是“同一树层上的使用过”,如何判断同一树层上元素(

    2024年02月14日
    浏览(42)
  • 【LeetCode动态规划#08】完全背包问题实战与分析(零钱兑换II--求组合、组合总和IV--求排列)

    力扣题目链接(opens new window) 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 示例 1: 输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 示例 2: 输入: amount = 3

    2023年04月19日
    浏览(42)
  • 【算法与数据结构】112、LeetCode路径总和

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题通过计算根节点到叶子节点路径上节点的值之和,然后再对比目标值。利用文章【算法和数据结构】257、LeetCode二叉树的所有路径中的递归算法。 这里要注意,默认路径之和是

    2024年02月11日
    浏览(53)
  • 算法 DAY44 动态规划6 完全背包 518. 零钱兑换 II 377. 组合总和 Ⅳ

    有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品都有无限个(也就是可以放入背包多次),求解将哪些物品装入背包里物品价值总和最大。 完全背包和01背包问题唯一不同的地方就是,每种物品有无限件。 动规五步曲来分

    2024年02月01日
    浏览(53)
  • 【算法】递归、回溯、剪枝、dfs 算法题练习(组合、排列、总和问题;C++)

    后面的练习是接着下面链接中的文章所继续的,在对后面的题练习之前,可以先将下面的的文章进行了解👇: 【算法】{画决策树 + dfs + 递归 + 回溯 + 剪枝} 解决排列、子集问题(C++) 思路 题意分析 :要求根据给出的数字,算出合法的括号组成个数。根据题目,我们可以总

    2024年02月22日
    浏览(50)
  • 力扣算法刷题Day44|动态规划:完全背包问题 零钱兑换II 组合总和Ⅳ

    力扣题目:#518.零钱兑换II(完全背包组合问题) 刷题时长:7min 解题方法:动态规划(完全背包) 复杂度分析 时间复杂度: O(mn),其中 m 是amount,n 是 coins 的长度 空间复杂度: O(m) 问题总结 对递推公式的理解 本题收获 题意转换:纯完全背包是凑成背包最大价值是多少,而本

    2024年02月13日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包