LeetCode 40.Combination Sum II (组合总和II）

朱雀 2022-05-11 04:12 186阅读 0赞

题目描述：

给定一个数组 `candidates` 和一个目标数 `target` ，找出 `candidates` 中所有可以使数字和为 `target` 的组合。

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

**说明：**

*  所有数字（包括目标数）都是正整数。
 *  解集不能包含重复的组合。

示例：

输入: candidates = [10,1,2,7,6,1,5], target = 8,
    所求解集为:
    [
      [1, 7],
      [1, 2, 5],
      [2, 6],
      [1, 1, 6]
    ]

输入: candidates = [2,5,2,1,2], target = 5,
    所求解集为:
    [
      [1,2,2],
      [5]
    ]

Accepted C++ Solution:

class Solution {
    public:
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
            sort(candidates.begin(),candidates.end());
            vector<vector<int>> res;
            vector<int> combination;
            combinationSum2(candidates, target, res, combination, 0);
            return res;
        }
    private:
        void combinationSum2(vector<int> &candidates, int target, vector<vector<int>> &res, vector<int> &combination,int begin) {
            if(!target) {
                res.push_back(combination);
                return;
            }
            for(int i = begin; i != candidates.size() && target >= candidates[i]; ++i)
                if(i == begin || candidates[i] != candidates[i-1]) { //跳过重复元素
                    combination.push_back(candidates[i]);
                    combinationSum2(candidates,target - candidates[i],res, combination, i+1);
                    combination.pop_back();
                }
        }
    };

和39题一样的方法，不过是增加一个条件，不使用重复的元素。

发表评论取消回复

表情：

评论列表（有 0 条评论，186人围观）

还没有评论，来说两句吧...

相关阅读

相关 ii 组合总和_40.组合总和II

题目给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的

迷南。/ 2023年01月09日 01:08/ 0 赞/ 158 阅读

相关 LeetCode | 0040. Combination Sum II组合总和 II【Python】

Problem [LeetCode][] Given a collection of candidate numbers (`candidates`) and a ta

缺乏、安全感/ 2022年12月05日 12:08/ 0 赞/ 109 阅读

相关 LeetCode 40. 组合总和 II

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

怼烎@/ 2022年11月01日 15:59/ 0 赞/ 166 阅读

相关 LeetCode40——Combination Sum II

LeetCode40——Combination Sum II 与上一题[Combination Sum][]类似，只不过是有放回的取。这题最关键的就是去重。所谓去重，不是

浅浅的花香味﹌/ 2022年08月09日 09:39/ 0 赞/ 141 阅读

相关 leetcode 40. Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique com

爱被打了一巴掌/ 2022年07月29日 08:57/ 0 赞/ 149 阅读

相关 [Leetcode][python]Combination Sum II/组合总和 II

题目大意在一个数组（存在重复值）中寻找和为特定值的组合。+ 注意点：所有数字都是正数组合中的数字要按照从小到大的顺序原数组中的数字只可以出现一次

桃扇骨/ 2022年06月08日 09:11/ 0 赞/ 178 阅读

相关 LeetCode——组合总和II（Combination Sum II）

题目：给定一个数组 `candidates` 和一个目标数 `target` ，找出 `candidates` 中所有可以使数字和为 `target` 的组合。 `c

﹏ヽ暗。殇╰゛Y/ 2022年05月14日 04:40/ 0 赞/ 179 阅读

相关 LeetCode 40.Combination Sum II (组合总和II）

题目描述：给定一个数组 `candidates` 和一个目标数 `target` ，找出 `candidates` 中所有可以使数字和为 `target` 的组合。 `c

朱雀/ 2022年05月11日 04:12/ 0 赞/ 186 阅读

相关【Leetcode】40. Combination Sum II

Given a collection of candidate numbers (`candidates`) and a target number (`target`), f

逃离我推掉我的手/ 2022年03月09日 08:40/ 0 赞/ 140 阅读

相关 [LeetCode]40.Combination Sum II

【题目】 Given a collection of candidate numbers (C) and a target number (T), find all un

秒速五厘米/ 2022年02月01日 18:53/ 0 赞/ 174 阅读