Skip to content

Instantly share code, notes, and snippets.

@thejsj
Last active September 28, 2020 17:54
Show Gist options
  • Save thejsj/291acdd7048c161ae56d549d5e2033df to your computer and use it in GitHub Desktop.
Save thejsj/291acdd7048c161ae56d549d5e2033df to your computer and use it in GitHub Desktop.
Combinations
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)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment