`

Combination Sum II(c++实现)

 
阅读更多

 

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

  • All numbers (including target) will be positive integers.
  • Elements in a combination (a1a2, � , ak) must be in non-descending order. (ie, a1 ? a2 ? � ? ak).
  • The solution set must not contain duplicate combinations.

 

For example, given candidate set 10,1,2,7,6,1,5 and target 8
A solution set is: 
[1, 7] 
[1, 2, 5] 
[2, 6] 
[1, 1, 6] 

 

 

class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        vector<vector<int> > ret;
        if(target <= 0) return ret;
        if(num.size() == 0) return ret;
        sort(num.begin(), num.end());
        vector<int> tmp;
        iter(num, target, 0, tmp, ret);
        return ret;
    }
    
    void iter(vector<int> &num, int target, int beg, vector<int> tmp, vector<vector<int> > &ret) {
        if(target == 0) {
            ret.push_back(tmp);
            return;
        }
        if(target > 0) {
            for(int i = beg; i < num.size(); ++i) {
                if(i == beg || num[i] != num[i-1]) {
                    tmp.push_back(num[i]);
                    iter(num, target-num[i], i+1, tmp, ret);
                    tmp.pop_back();
                }
            }
        }
    }
    
};

 

 

 欢迎关注微信公众号——计算机视觉 

 

0
3
分享到:
评论

相关推荐

    java-leetcode题解之Combination Sum II.java

    在Java中实现Combination Sum II的解法需要掌握基本的Java语法,递归的实现方式,以及对Java集合框架中的常用数据结构(如List和Set)的应用。实际上,掌握了回溯算法的基本原理之后,面对类似的组合求和问题就能够...

    java-leetcode题解之Combination Sum.java

    Java实现LeetCode题解之 Combination Sum Java代码示例和详解 在数据结构与算法的学习过程中,组合求和问题是一项基础且常见的问题。LeetCode中的Combination Sum问题正是一个考察回溯法的经典题目。这个问题的目标...

    C语言-leetcode题解之40-combination-sum-ii.c

    在这篇文章中,我们将深入探讨C语言解决leetcode上的第40题——"Combination Sum II"的详细过程。 首先,我们有必要理解题目的基本要求。题目是给出一组数字,每个数字只能使用一次,要求找出所有可能的数字组合,...

    js-leetcode题解之40-combination-sum-II.js

    首先,“js-leetcode题解之40-combination-sum-II.js”是一份JavaScript编程语言实现的LeetCode算法题解。LeetCode是一个在线编程平台,主要提供算法训练和面试准备题目,题目涵盖从初级到高级的不同难度级别。这道...

    java-leetcode题解之Combination Sum IV.java

    Combination Sum IV 题目是 LeetCode 平台上的一道算法题目,主要考察动态规划算法的应用。...以上就是 Combination Sum IV 题目的详细解题思路和 Java 实现,此题对于理解动态规划和组合问题具有很好的帮助作用。

    java-leetcode题解之Combination Sum III.java

    其中,“Combination Sum III”是其中的一道典型的回溯算法题。 “Combination Sum III”题目要求给定一个范围,找出所有相加之和为特定值的k个数的组合。在这个问题中,所有数字必须是唯一的,且数字范围限制在1到...

    Coding Interview In Java

    239 Combination Sum II 579 240 Combination Sum III 581 241 Combinations 583 242 Letter Combinations of a Phone Number 587 243 Restore IP Addresses 589 244 Reverse Integer 591 245 Palindrome Number 593

    c++-c++编程基础之leetcode题解第40题组合总和II.zip

    本题解聚焦于LeetCode的第40题,名为"Combination Sum II",这是一道关于组合问题的典型算法题。在这个问题中,我们需要找出所有可能的组合,使得组合中的数字之和等于给定的目标值。以下是对这个问题的详细分析和...

    js-leetcode题解之39-combination-sum.js

    本篇题解将针对LeetCode上的一道经典题目“Combination Sum”进行详细阐述,并提供js语言的解决方案。 “Combination Sum”问题的描述是这样的:给定一个无重复元素的数组 `candidates` 和一个目标数 `target`,找...

    python-leetcode题解之216-Combination-Sum-III.py

    特别是算法题目,如216题——Combination Sum III,对于锻炼编程者的算法思维和代码实现能力有着重要作用。 Combination Sum III这道题目要求解的是找出所有和为特定值的组合,其中每个数字仅能使用一次,这些数字...

    C语言-leetcode题解之39-combination-sum.c

    LeetCode题解之39-Combination Sum是一个典型的C语言算法问题,主要考察候选者对回溯算法的理解和实现能力。该问题的具体内容是找出所有相加之和为给定目标数target的组合,且每组中每个数字可以重复使用多次。解决...

    java-leetcode题解之039-Combination-Sum

    java入门 java_leetcode题解之039_Combination_Sum

    求子集c++算法,经典

    ### 求子集C++算法详解 ...本文通过分析提供的C++代码,详细解释了递归求子集算法的工作原理、实现细节以及时间空间复杂度等关键概念。希望本文能帮助读者更好地理解和掌握求子集问题的相关知识。

    c++ 排列组合算法,代码简单

    ### C++中的排列组合算法实现 #### 1. 排列算法(Permutation) 在C++中,排列算法通常用于生成一组元素的所有可能顺序。在给定的代码中,排列算法通过递归方式实现。其主要步骤包括: - **初始化**: 定义一个数组...

    基于C++实现通过组合函数计算n个元素中由k个元素组合的子集个数

    在C++中实现这个功能,可以帮助我们解决很多组合优化问题,例如计数、排列组合等。本篇文章将详细讲解如何用C++来计算n个元素中由k个元素组成的子集个数,以及涉及的相关知识点。 首先,我们需要理解组合的基本定义...

    c++-c++编程基础之leetcode题解第39题组合总和.zip

    C++代码实现如下: ```cpp vector&lt;vector&lt;int&gt;&gt; combinationSum(vector&lt;int&gt;& candidates, int target) { vector&lt;vector&lt;int&gt;&gt; result; vector&lt;int&gt; current; backtrack(candidates, target, result, current, 0...

    手稿_V1.015

    这个问题来源于LeetCode的一个经典题目——“组合总和II”(Combination Sum II),它要求我们找到一组数组中的所有可能组合,使得这些数字的和等于给定的目标数,但每个数字只能使用一次。 首先,我们要理解“剪枝”...

Global site tag (gtag.js) - Google Analytics