组合总和

1. 题目描述

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

candidates 中的数字可以无限制重复被选取。

2. 思路

1. 思路一
   • DFS
   • 选择一个数后把target减去当前数，继续下一个（注意可以重复选）

3. 实现

3.1. DFS

func combinationSum(candidates []int, target int) [][]int {
    var res [][]int
    var path []int
    combinationSumDFS(candidates, target, &path, &res)
    return res
}

func combinationSumDFS(candidates []int, target int, path *[]int, res *[][]int) {
    if target < 0 {
        return 
    }

    if target == 0 {
        dst := make([]int,len(*path))
        copy(dst, *path)
        sort.Ints(dst)
        if !exists(dst, res) {
            *res = append(*res, dst)
        }
        return
    }

    for _, num := range candidates {
        *path = append(*path, num)
        combinationSumDFS(candidates, target-num, path, res)
        *path = (*path)[:len(*path)-1]
    }
}

func exists(path []int, res *[][]int) bool {
    for _, current := range *res {
        if reflect.DeepEqual(path, current) {
            return true
        }
    }
    return false
}

4. 参考

• 39. 组合总和 - 力扣（LeetCode）