0039.组合总和

https://leetcode.cn/problems/combination-sum/

方法一：回溯

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。

func combinationSum(candidates []int, target int) [][]int {
	ans, n := [][]int{}, len(candidates)
	var backtrack func(start, now int, data []int)
	backtrack = func(start, now int, data []int) {
		if now == target {
			ans = append(ans, append([]int{}, data...))
			return
		} else if now > target || start >= n {
			return
		}
		for i := start; i < n; i++ {
			data = append(data, candidates[i])
			backtrack(i, now+candidates[i], data)
			data = data[:len(data)-1]
		}
	}
	backtrack(0, 0, []int{})
	return ans
}