package main

import "sort"

// 像这种需要记录明确组合集合的，没什么好剪枝或dp的，因为剪枝和dp都会丢失一部分的信息，而这种题目要求构建树的信息是全量的
func combinationSum2(candidates []int, target int) (res [][]int) {
	sort.Ints(candidates)
	trace := make([]int,0,0)
	var depth func(a , sum, floor int)
	depth = func(idx, sum, floor int) {
		if sum > target {
			return
		}
		if sum == target {
			res = append(res, append([]int{}, trace...))
		}
		for i := idx ; i < len(candidates) ; i ++ {
			if i > idx && candidates[i-1] == candidates[i]  {
				continue
			}
			trace = append(trace, candidates[i])
			sum += candidates[i]
			depth(i+1 ,  sum, floor + 1)
			trace = trace[:len(trace)-1]
			sum -= candidates[i]
		}
	}
	depth(0, 0, 0)
	return res
}