Combination Sum II

Description

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:

All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
  [1,2,2],
  [5]
]

Solution

与上一篇 Combination Sum 几乎一毛一样。只是多了一步去重操作。

func combinationSum2(candidates []int, target int) [][]int {
    sort.Ints(candidates)

    return doCombinationSum(candidates, target)
}

func doCombinationSum(candidates []int, target int) [][]int {
    res := [][]int{}

    if len(candidates) == 0 {
        return res
    }

    t := target - candidates[0]

    if t == 0 {
        res = append(res, []int{candidates[0]})
    } else if t > 0 {
        res = doCombinationSum(candidates[1:], t)
        for i, v := range res {
            res[i] = append([]int{candidates[0]}, v...)
        }
    }

    // 为了去重
    for len(candidates) > 1 && candidates[0] == candidates[1] {
        candidates = candidates[1:]
    }

    res = append(res, doCombinationSum(candidates[1:], target)...)

    return res
}

Similar Problem