Skip to main content

39. Combination Sum

分析

经典回溯问题 注意 go语言和js很像,注意自己管理栈内存

题解

func combinationSum(candidates []int, target int) [][]int {
sort.Ints(candidates)
ans := [][]int{}

var dfs func(sum, start int, temp []int)
dfs = func(sum, start int, temp []int) {
if sum > target {
return
}
if sum == target {
copyTemp := make([]int, len(temp))
copy(copyTemp, temp)
ans = append(ans, copyTemp)
}
for i := start; i < len(candidates); i++ {
temp = append(temp, candidates[i])
dfs(sum+candidates[i], i, temp)
temp = temp[:len(temp)-1]
}
}

dfs(0, 0, []int{})

return ans
}