39. 组合总和

https://leetcode-cn.com/problems/combination-sum/

解法一：回溯

经典回溯。为防止重复先排序，用i遍历candidates[start:]，尝试将每个数加入tmplist，因为回头会引起重复，因此递归向后，下一轮start=i。

在递归算法中设置条件，若超过target则返回，等于则将结果写入res，小于则继续添加。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        self.res = []    #全局结果
        tmpList = []    #工作数组
        candidates.sort()  #先排序
        self.backtrack(tmpList, candidates, target, 0)
        return self.res
    
    #回溯函数，remain为当前与target的差距，start为候选集中的起始位置
    def backtrack(self, tmpList, candidates, remain, start):
        if remain < 0:  #超了，返回
            return
        elif remain == 0:  #恰好等于,记录结果，并返回
            self.res.append(list(tmpList))  #创建一个新的list再写入，否则res会随tmplist改变
            return  #其实不返回也没事，因为函数到这之后也会退出
        else:  #还不够，继续递归
            for i in range(start, len(candidates)):  #从start开始，对每个数遍历
                tmpList.append(candidates[i])  #尝试先加入tmplist
                #递归，注意最后一个参数不是i+1，因为元素可以重复使用
                self.backtrack(tmpList, candidates, remain - candidates[i], i)  
                tmpList.pop()  #不符合则回退

回溯可以简化，参考回溯总结

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        self.res = []
        tmpList = []
        candidates.sort()
        self.backtrack(tmpList, candidates, target, 0)
        return self.res

    def backtrack(self, tmpList, candidates, remain, start):
        if remain < 0:
            return
        elif remain == 0:
            self.res.append(list(tmpList))
        else:
            for i in range(start, len(candidates)):
                self.backtrack(tmpList + [candidates[i]], candidates, remain - candidates[i], i) 

2020.3.25

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(tmp, sum, start):
            if sum > target:
                return
            elif sum == target:
                res.append(list(tmp))
                return
            for i in range(start, n):
                num = candidates[i]
                dfs(tmp + [num], sum + num, i)
        
        candidates.sort()
        n = len(candidates)
        res = []
        dfs([], 0, 0)
        return res

js：

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
  var dfs = function(tmp, sum, start) {
    if (sum > target) return
    else if (sum === target) {
      res.push(Array.from(tmp))
      return
    }
    for (let i = start; i < n; i++) {
      let num = candidates[i]
      tmp.push(num)
      dfs(tmp, sum + num, i)
      tmp.pop()
    }
  }
  const n = candidates.length
  const res = []
  candidates.sort((a,b) => a - b)
  dfs([], 0, 0)
  return res
};