0040.组合总和 II

方法一：排序 + 回溯

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

func combinationSum2(candidates []int, target int) [][]int {
	sort.Ints(candidates)
	ans := [][]int{}
	var backtrack func(start, sum int, data []int)
	backtrack = func(start, sum int, data []int) {
		// base case
		if sum == target {
			ans = append(ans, append([]int{}, data...))
			return
		} else if start == len(candidates) || sum > target {
			return
		}

		for i := start; i < len(candidates); i++ {
			if i > start && candidates[i] == candidates[i-1] {
				continue
			}
			data = append(data, candidates[i])
			backtrack(i+1, sum+candidates[i], data)
			data = data[:len(data)-1]
		}
	}
	backtrack(0, 0, []int{})
	return ans
}