LC 39. 组合总和（回溯）

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
}