package main

import (
	"sort"
)

func combinationSumIter(candidates []int, target int, beg int, last []int, res *[][]int) {
	if target == 0 {
		*res = append(*res, last)
	}
	for i := beg; i < len(candidates) && candidates[i] <= target; i++ {
		// if don't copy solution, iteration'll fail
		// go slice is just like a ptr
		solution := make([]int, len(last))
		copy(solution, last)
		solution = append(solution, candidates[i])
		combinationSumIter(candidates, target-candidates[i], i, solution, res)
	}
}

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

/* func main() {
	a1 := []int{2, 3, 6, 7}
	fmt.Println(combinationSum(a1, 7))
	a2 := []int{1, 2}
	fmt.Println(combinationSum(a2, 4))
	a3 := []int{8, 7, 4, 3}
	fmt.Println(combinationSum(a3, 11))
	a4 := []int{7, 3, 2}
	fmt.Println(combinationSum(a4, 18))
} */