1. 题目描述

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

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

说明：

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

示例 1：

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

示例 2：

  1. 输入：candidates = [2,3,5], target = 8,
  2. 所求解集为：
  3. [
  4.   [2,2,2,2],
  5.   [2,3,3],
  6.   [3,5]
  7. ]

提示：

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

  • 1 <= target <= 500

    2. 解题思路

    这道题目和77题差不多，实现思路都是回溯+剪枝，唯一不一样的地方就是这里求得是所有组合的总和，我们初始化另一个sum保存当前还需要的总和的值，在递归的过程中，不断减少sum的值，直至最后和target相等，就将组合保存在结果中。

    3. 代码实现

    1. /**
    2. * @param {number[]} candidates
    3. * @param {number} target
    4. * @return {number[][]}
    5. */
    6. var combinationSum = function(candidates, target) {
    7.   const res = []
    8.   let sum = 0
    10.   const dfs = (start, arr) => {
    11.       if(sum >= target){
    12.           if(sum === target){
    13.               res.push([...arr])
    14.           }
    15.           return 
    16.       }
    18.       for(let i = start; i < candidates.length; i++){
    19.           sum += candidates[i]
    20.           arr.push(candidates[i])
    21.           dfs(i, arr)
    22.           sum -= candidates[i]
    23.           arr.pop()
    24.       }
    25.   }
    26.   dfs(0, [])
    27.   return res
    28. };

    4. 提交结果

    39. 组合总和 - 图1