原文:39. 组合总和(力扣 面试题) - 每天一个JavaScript小知识@Js中文网 · 码农进阶题库

原文地址:https://www.javascriptc.com/interview-tips/zh_cn/leetcode/leetcode-javascript-solution-039/

题目:

难度:Middle

相关话题:数组回溯算法

给定一个无重复元素 的数组 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]
]

思路:

回溯,每一次回溯,遍历当前数组尝试每一个值。

由于要求不包含重复组合,不使用hash的话,就对每一次回溯都只遍历上一次遍历最后的索引i之后的值;

但题目提示每个值都能重复使用无限次,因此每次遍历都从上一个i开始,既可以保证没有重复的组合,也确保每个值都尽可能的多用。

/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
  let result=[]
  backtrack([],target,0)
  return result

  function  backtrack(temp,rest,start){
    if(rest<0)return
    if(rest===0)result.push(temp.slice())
    for(let i=start;i<candidates.length;i++){
      temp.push(candidates[i])
      backtrack(temp,rest-candidates[i],i)
      temp.pop()
    }
  }
};