LeetCode 40. Combination Sum II

Combination Sum II.go

func combinationSum2(candidates []int, target int) [][]int {
	sort.Ints(candidates)
	var result [][]int
	var dfs func([]int, int, []int, int)
	dfs = func(candidates []int, startIndex int, currentSet []int, newTarget int) {
		if newTarget == 0 {
			newSet := make([]int, len(currentSet))
			copy(newSet, currentSet)
			result = append(result, newSet)
			return
		}
		if newTarget < 0 {
			return
		}
		for i := startIndex; i < len(candidates); i++ {
			if i > startIndex && candidates[i] == candidates[i-1] {
				continue
			}
			currentSet = append(currentSet, candidates[i])
			dfs(candidates, i+1, currentSet, newTarget-candidates[i])
			currentSet = currentSet[:len(currentSet)-1]
		}
	}
	dfs(candidates, 0, make([]int, 0), target)
	return result
}