40. 组合总和 II

题目描述

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

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

注意: 解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:

[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:

[
[1,2,2],
[5]
]

提示:

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

解法一：回溯

正确代码 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


func combinationSum2(candidates []int, target int) [][]int {
    if len(candidates) == 0 {
        return [][]int{}
    }
    var c []int
    var res [][]int
    sort.Ints(candidates)
    findCombinationSum2(candidates, target, 0, c, &res)
    return res
}

func findCombinationSum2(nums []int, target int, index int, c []int, res *[][]int) {
    if target <= 0 {
        if target == 0 {
            b := make([]int, len(c))
            copy(b, c)
            *res = append(*res, b)
        }
        return
    }

    for i := index; i < len(nums); i++ {
        if i > index && nums[i] == nums[i-1] {
            continue
        }
        if nums[i] > target {
            break
        }
        c = append(c, nums[i])
        findCombinationSum2(nums, target-nums[i], i+1, c, res)
        c = c[:len(c)-1]
    }
}

正确代码 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


func combinationSum2(candidates []int, target int) [][]int {
    var ans [][]int
    var tmp []int
    n := len(candidates)
    sort.Ints(candidates)
    var backtracking func(idx, curSum int)
    backtracking = func(idx, curSum int) {
        if curSum == target {
            replica := make([]int, len(tmp))
            copy(replica, tmp)
            ans = append(ans, replica)
            return
        }
        if idx >= n || curSum > target {
            return
        }

        for i := idx; i < n; i++ {
            if i == idx || candidates[i] != candidates[i-1] {
                tmp = append(tmp, candidates[idx])
                backtracking(i+1, curSum+candidates[idx])
                tmp = tmp[:len(tmp)-1]
            }
        }
    }
    backtracking(0, 0)
    return ans
}