LeetCode 39.Combination Sum (组合总和)

我会带着你远行 2022-05-11 04:10 167阅读 0赞

题目描述：

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

`candidates`中的数字可以无限制重复被选取。

**说明：**

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

示例：

输入: candidates = [2,3,6,7], target = 7,
    所求解集为:
    [
      [7],
      [2,2,3]
    ]

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

Accepted C++ Solution:

class Solution {
    public:
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            sort(candidates.begin(),candidates.end());
            vector<vector<int>> res;
            vector<int> combination;
            combinationSum(candidates, target, res, combination, 0);
            return res;
        }
    private:
        void combinationSum(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) {
                combination.push_back(candidates[i]);
                combinationSum(candidates, target-candidates[i], res, combination, i);
                combination.pop_back();
            }
        }
    };

使用回溯的方法解决。

发表评论取消回复

表情：

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

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

相关阅读

相关 Combination Sum（C++组合总和）

解题思路：（1）回溯，下一个仍为i class Solution { public: vector<vector<int>> vec;

Love The Way You Lie/ 2023年01月16日 02:16/ 0 赞/ 289 阅读

相关 leetcode 39. Combination Sum | 39. 组合总和（Java）

题目 [https://leetcode.com/problems/combination-sum/][https_leetcode.com_problems_combi

ゝ一世哀愁。/ 2022年09月03日 07:28/ 0 赞/ 177 阅读

相关 LeetCode39——Combination Sum

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

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

相关 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 赞/ 181 阅读

相关 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 赞/ 195 阅读

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

题目大意给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 can

╰+哭是因爲堅強的太久メ/ 2022年06月08日 05:26/ 0 赞/ 196 阅读

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

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

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

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

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

我会带着你远行/ 2022年05月14日 02:59/ 0 赞/ 219 阅读

相关 LeetCode 39.Combination Sum (组合总和)

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

我会带着你远行/ 2022年05月11日 04:10/ 0 赞/ 168 阅读

相关【Leetcode】39. Combination Sum

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

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