[Medium]LeetCode#40. 组合总和 II

[Medium]LeetCode#40. 组合总和 II

题目原地址

给定一个数组 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]
]
  • 基本算法,求除本身外剩余数的组合是否等于target – 本身,在原基础上改造
func combinationSum2(candidates []int, target int) [][]int {
    sort.Ints(candidates)
    return dfs2(candidates, target)
}

func dfs2(candidates []int, target int) [][]int {
    l := len(candidates)
    if l == 0 {
        return nil
    }
    var res [][]int
    next := target - candidates[0] // 下一个和
    switch {
    case next < 0:
        return nil
    case next == 0:
        return [][]int{{candidates[0]}}
    case next > 0: // 寻找子和的任意组合
        combines := dfs2(candidates[1:], next)
        for _, combine := range combines {
            res = append(res, append(combine, candidates[0])) // 将子和的任意组合添加到解中
        }
    }
    s := 1
    for i := 1; i < l; i++ {
        if candidates[i] == candidates[0] {
            s = i+1
        } else {
            break
        }
    }
    res = append(res, dfs2(candidates[s:], target)...) // 在后续数组中尝试和为 target 的组合
    return res
}