leetcode Combination Sum解题报告

偏执的太偏执、 2022-08-09 11:57 155阅读 0赞

# 题目 #

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

The same repeated number may be chosen from C unlimited number of times.

Note:  
All numbers (including target) will be positive integers.  
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).  
The solution set must not contain duplicate combinations.  
For example, given candidate set 2,3,6,7 and target 7,  
A solution set is:  
\[7\]  
\[2, 2, 3\]  
题目来源：[https://leetcode.com/problems/combination-sum/][https_leetcode.com_problems_combination-sum]

# 分析 #

回朔法。

# 代码 #

class Solution {
    private:
        vector<vector<int>> ans;
    public:
        void combinationSumHelp(vector<int>& candidates, int target, int start, vector<int>& tmpComb) {
            if(target == 0){
                ans.push_back(tmpComb);
                return;
            }
            if(target < 0)
                return;
            int len = candidates.size();
            for(int i = start; i < len; i++){
                tmpComb.push_back(candidates.at(i));
                combinationSumHelp(candidates, target - candidates.at(i), i, tmpComb);
                tmpComb.pop_back();
            }
        }
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            sort(candidates.begin(), candidates.end());
            vector<int> tmpComb;
            combinationSumHelp(candidates, target, 0, tmpComb);
            return ans;
        }
    };

[https_leetcode.com_problems_combination-sum]: https://leetcode.com/problems/combination-sum/

发表评论取消回复

表情：

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

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

相关阅读

相关 [leetcode] 371. Sum of Two Integers 解题报告

题目链接: https://leetcode.com/problems/sum-of-two-integers/ Calculate the sum of two integ

╰+攻爆jí腚メ/ 2022年09月25日 07:18/ 0 赞/ 158 阅读

相关 leetcode Combination Sum解题报告

题目 Given a set of candidate numbers (C) and a target number (T), find all unique comb

偏执的太偏执、/ 2022年08月09日 11:57/ 0 赞/ 156 阅读

相关【MySQL】【leetcode】 Combine Two Tables解题报告

题目 Table: Person +-------------+---------+ | Column Name | Type | +---------

╰半夏微凉°/ 2022年08月09日 10:58/ 0 赞/ 141 阅读

相关 LeetCode39——Combination Sum

LeetCode39——Combination Sum 题意：打个比方，现在盒子里面有小球，球上有数字，现在给定一个target，要求有放回的从盒子里面取小球，要求数字加

た入场券/ 2022年08月09日 09:38/ 0 赞/ 14 阅读

相关 3Sum——解题报告

【题目】 Given an array S of n integers, are there elements a, b, c in S such that a

ゞ浴缸里的玫瑰/ 2022年08月08日 06:12/ 0 赞/ 237 阅读

相关 leetcode 39. Combination Sum

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

小灰灰/ 2022年07月29日 08:51/ 0 赞/ 175 阅读

相关 [leetcode javascript解题]Combination Sum

leetcode第39题Combination Sum描述如下： > Given a set of candidate numbers (C) (without duplic

￡神魔★判官ぃ/ 2022年07月13日 08:18/ 0 赞/ 140 阅读

相关 leetcode:39. Combination Sum

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find

女爷i/ 2022年07月12日 11:49/ 0 赞/ 183 阅读

相关【Leetcode】39. Combination Sum

Given a set of candidate numbers (`candidates`) (without duplicates) and a target number

╰+攻爆jí腚メ/ 2022年03月09日 05:08/ 0 赞/ 193 阅读

相关 leetcode--Combination Sum

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

约定不等于承诺〃/ 2021年10月16日 01:12/ 0 赞/ 264 阅读