package main

import (
	"sort"
)

func combinationSum2Iter(candidates []int, target int, last []int, beg int, res *[][]int) {
	if target == 0 {
		*res = append(*res, last)
		return
	}
	for i := beg; i < len(candidates) && candidates[i] <= target; i++ {
		// method to remove duplicated solutions
		if i > beg && candidates[i] == candidates[i-1] {
			continue
		}
		solution := make([]int, len(last))
		copy(solution, last)
		solution = append(solution, candidates[i])
		combinationSum2Iter(candidates, target-candidates[i], solution, i+1, res)
	}
}

func combinationSum2(candidates []int, target int) [][]int {
	res := make([][]int, 0)
	sort.Ints(candidates)
	combinationSum2Iter(candidates, target, []int{}, 0, &res)
	return res
}

/* func main() {
	a1 := []int{10, 1, 2, 7, 6, 1, 5}
	fmt.Println(combinationSum2(a1, 8))
} */