LC 39. 组合总和（回溯）

题目

思路

这题可以直接用DFS暴力搜也可以过。

可以采用回溯 剪枝缩短一下时间 对于[2, 3, 6 ,7] 可以让target减去每个数，然后依次减下去得到0这条路径就是一个答案。

但是这样会产生四个正确的路径，因为有三个重复的，产生重复的原因为在别的路径中重复使用了之前使用过的路径，所以在后面的路径中不再使用前面的数即可解决重复的问题

代码语言：javascript复制

var list [][]int

// begin为每次循环遍历的起点，设置begin为了不重复使用前面使用过的数
func dfs(candidates []int, target int, begin int, sil []int) {
    if target == 0 {
        arr := make([]int, len(sil))
        copy(arr, sil)
        list = append(list, arr)
        return
    }
    for i := begin; i < len(candidates); i   {
        if target-candidates[i] >= 0 {
            arr := append(sil, candidates[i])
            dfs(candidates, target-candidates[i], i, arr)
        }
    }
}

func combinationSum(candidates []int, target int) [][]int {
    list = make([][]int, 0)
    sil := []int{}
    dfs(candidates, target, 0, sil)
    return list
}

dfs target

0 人点赞