141 - 39 组合总和

题目

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

https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/

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

        def helper(candidates, begin, target):
            if target == 0:
                res.append(path[:])
            for index in range(begin, len(candidates)):
                residue = target - candidates[index]
                if residue < 0:
                    break
                path.append(candidates[index])
                helper(candidates, index, residue)
                path.pop()

        helper(candidates, 0, target)
        return res

Runtime: 48 ms, faster than 99.49% of Python3 online submissions for Combination Sum.

Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Combination Sum.

var combinationSum = function(candidates, target) {
  if (candidates.length === 0) {
    return []
  }
  candidates.sort((a, b) => a - b)
  path = []
  res = []
  const helper = function(start, target) {
    if (target === 0) {
      res.push(path.slice())
    }
    for (let i = start; i < candidates.length; i++) {
      const residue = target - candidates[i]
      if (residue < 0) {
        break
      }
      path.push(candidates[i])
      helper(i, residue)
      path.pop()
    }
  }
  helper(0, target)
  return res
};

Runtime: 76 ms, faster than 64.33% of JavaScript online submissions for Combination Sum.

Memory Usage: 36.7 MB, less than 66.67% of JavaScript online submissions for Combination Sum.

func combinationSum(candidates []int, target int) [][]int {
    if len(candidates) == 0 {
        return nil
    }
    result := make([][]int, 0)
    path := make([]int, 0)
    sort.Ints(candidates)
    var helper func(int, int)
    helper = func(start, target int) {
        if target == 0 {
            tmp := make([]int, len(path))
            copy(tmp, path)
            result = append(result, tmp)
        }
        for i := start; i < len(candidates); i++ {
            diff := target - candidates[i]
            if diff < 0 {
                return
            }
            path = append(path, candidates[i])
            helper(i, diff)
            path = path[:len(path)-1]
        }
    }
    helper(0, target)
    return result
}

Runtime: 4 ms, faster than 87.04% of Go online submissions for Combination Sum.

Memory Usage: 4 MB, less than 100.00% of Go online submissions for Combination Sum.

解法2

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

        def helper(i, temp, target):
            if target == 0:
                res.append(temp[:])
                return
            if i == len(candidates) or target < candidates[i]:
                return
            helper(i, temp+[candidates[i]], target - candidates[i])
            helper(i+1, temp, target)

        helper(0, [], target)
        return res

Runtime: 48 ms, faster than 99.49% of Python3 online submissions for Combination Sum.

Memory Usage: 12.9 MB, less than 100.00% of Python3 online submissions for Combination Sum.