【LeetCode 39】组合总和

深碍√TFBOYSˉ_ 2022-12-05 05:15 160阅读 0赞

#### 题目描述 ####

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

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

说明：

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

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

示例 2：

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

提示：

*  1 <= candidates.length <= 30
 *  1 <= candidates\[i\] <= 200
 *  candidate 中的每个元素都是独一无二的。
 *  1 <= target <= 500

#### 解题思路 ####

看到这道题目，似曾相识的感觉呢？昨天的每日一题：[【LeetCode 77】组合][LeetCode 77]，思路几乎是一模一样。也就是回溯+剪枝，唯一不一样的地方就是这里求得是所有组合的总和，我们初始化另一个sum保存当前还需要的总和的值，在递归的过程中，不断减少sum的值，直至最后和target相等，就将组合保存在结果中。

#### 代码实现 ####

/** * @param {number[]} candidates * @param {number} target * @return {number[][]} */
    var combinationSum = function(candidates, target) { 
        const res = []
        let sum = 0
    
        const dfs = (start, arr) => { 
            if(sum >= target){ 
                if(sum === target){ 
                    res.push([...arr])
                }
                return 
            }
    
            for(let i = start; i < candidates.length; i++){ 
                sum += candidates[i]
                arr.push(candidates[i])
                dfs(i, arr)
                sum -= candidates[i]
                arr.pop()
            }
        }
        dfs(0, [])
        return res
    };

#### 提交结果 ####

![在这里插入图片描述][2020090911504082.png]

[LeetCode 77]: https://cuggz.blog.csdn.net/article/details/108465322
[2020090911504082.png]: /images/20221123/4e7b6c8ad3d94e13a72c6e9a5b4b82b2.png?