Combinations

combination.go

package main

import (
	"fmt"
	"reflect"
	"sort"
)

func sum(nums []int) int {
	total := 0
	for _, n := range nums {
		total += n
	}
	return total
}

func iterate(result []int, candidates []int, target int, results *[][]int) {

	s := sum(result)

	// If the sume of result is equal to target
	if s == target {
		found := false

		for _, existing_result := range *results {
			if reflect.DeepEqual(existing_result, result) {
				found = true
			}
		}

		if !found {
			*results = append(*results, result)
		}

		return
	}

	if s > target {
		return
	}

	for i, candidate := range candidates {
		result_copy := make([]int, len(result))
		copy(result_copy, result)
		new_result := append(result_copy, candidate)
		new_candidates := append([]int{}, candidates[i+1:]...)
		iterate(new_result, new_candidates, target, results)
	}
	return
}

func combinationSum2(candidates []int, target int) [][]int {
	// Create results slice
	results := [][]int{}

	// If candidates is empty, return
	if len(candidates) == 0 {
		return results
	}

	sort.Ints(candidates)

	// Call iterate funcction
	for i, candidate := range candidates {
		// Get a candidates slice without the given candidate
		c := append([]int{}, candidates[i+1:]...)
		result := []int{candidate}
		iterate(result, c, target, &results)
	}

	// return results
	return results
}

func main() {
	candidates := []int{3, 1, 3, 5, 1, 1}
	result1 := combinationSum2(candidates, 8)
	// candidates := []int{1, 1, 2, 3, 4, 5}
	// result1 := combinationSum2(candidates, 5)
	fmt.Printf("%v\n", result1)

}