39.M 组合总和

Problem: 39. 组合总和

思路

回溯法。

此题与一般的回溯法的区别主要在于每个数字都可以选择多次，因此在进行递归操作时，下一步的start还是为i。

每次回溯时把当前元素加到路径中，然后把target减去当前元素的值，一直往下递归直到target小于0，此时说明该分支已经没有符合要求的路径。

Code

func combinationSum(candidates []int, target int) [][]int {
	var path []int
	var ans [][]int
	backtrack(candidates, target, 0, path, &ans)
	return ans
}

func backtrack(candidates []int, target int, start int, path []int, ans *[][]int) {
	if target == 0 {
		*ans = append(*ans, append([]int{}, path...))
		return
	}

	if target < 0 {
		return
	}

	for i := start; i < len(candidates); i++ {
		path = append(path, candidates[i])
		backtrack(candidates, target-candidates[i], i, path, ans)
		path = path[0 : len(path)-1]
	}
}