[Medium]LeetCode#39. 组合总和

[Medium]LeetCode#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]
]
  • 基本算法,求除本身外剩余数的组合是否等于target – 本身
func combinationSum(candidates []int, target int) [][]int {
    sort.Ints(candidates)
    return dfs(candidates, target)
}

func dfs(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 := dfs(candidates, next)
        for _, combine := range combines {
            res = append(res, append(combine, candidates[0])) // 将子和的任意组合添加到解中
        }
    }
    res = append(res, dfs(candidates[1:], target)...)// 在后续数组中尝试和为 target 的组合
    return res
}