19.组合的总数-回溯法

package main

// @solution-sync:begin
func combinationSum(candidates []int, target int) [][]int {
	result := make([][]int, 0)
	var dfs func(start int, temp []int, sum int)

	dfs = func(start int, temp []int, sum int) {
		if sum >= target {

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

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