142 - 40 组合总和2

题目

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

candidates 中的每个数字在每个组合中只能使用一次。

说明：

• 所有数字（包括目标数）都是正整数。

• 解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [ [1,2,2], [5] ]

解答

一样的回溯套路，需要跳过一下相同值，以及剪掉负数的分支

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

        def helper(begin, target, candidates):
            if target == 0:
                res.append(tmp[:])
            for i in range(begin, len(candidates)):
                if i > 0 and candidates[i] == candidates[i-1]:
                    continue
                diff = target - candidates[i]
                if diff < 0:
                    break
                tmp.append(candidates[i])
                newCand = candidates[:]
                newCand.pop(i)
                helper(i, diff, newCand)
                tmp.pop()
        helper(0, target, candidates)
        return res

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

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

https://leetcode.com/problems/combination-sum-ii/discuss/259449/golang

func combinationSum2(nums []int, target int) (result [][]int) {
    sort.Ints(nums)
    combinationSum2Helper(nums, nil, target, 0, 0, &result)
    return result
}

func combinationSum2Helper(nums, combo []int, target, sum, startIndex int, result *[][]int) {
    if sum == target {
        *result = append(*result, append([]int{}, combo...))
        return
    }
    for i := startIndex; i < len(nums) && (sum + nums[i]) <= target; i++ {
        if i != startIndex && nums[i] == nums[i - 1] { continue }
        combinationSum2Helper(nums, append(combo, nums[i]), target, sum + nums[i], i + 1, result)
    }
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for Combination Sum II.

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

var combinationSum2 = function(candidates, target) {
  candidates.sort((a, b) => a - b)
  let result = [],
    n = candidates.length

  const backtrack = function(start, target, list) {
    if (target === 0) {
      result.push(list)
    }
    for (let i = start; i < n; i++) {
      let diff = target - candidates[i]
      if (diff < 0) {
        break
      }
      if (i > start && candidates[i] === candidates[i - 1]) {
        continue
      }
      backtrack(i + 1, target - candidates[i], [...list, candidates[i]])
    }
  }

  backtrack(0, target, [])

  return result
}

Runtime: 72 ms, faster than 68.74% of JavaScript online submissions for Combination Sum II.

Memory Usage: 37.3 MB, less than 20.00% of JavaScript online submissions for Combination Sum II.