Skip to content

Instantly share code, notes, and snippets.

@nleiva
Created February 26, 2018 21:16
Show Gist options
  • Save nleiva/a21f427ec594c0c5259ef82aa1f0961e to your computer and use it in GitHub Desktop.
Save nleiva/a21f427ec594c0c5259ef82aa1f0961e to your computer and use it in GitHub Desktop.
Combinations (77) from https://leetcode.com/problems/combinations/description/ ....too compex :-(
// Slice implements sort.Interface
type Slice []int
func (a Slice) Len() int { return len(a) }
func (a Slice) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a Slice) Less(i, j int) bool { return a[i] < a[j] }
func combine(n int, k int) [][]int {
a := []int{}
for i := 1; i <= n; i++ {
a = append(a, i)
}
r := [][]int{}
m := make(map[string]bool)
r = append(r, a[:k])
for i := k; i < n; i++ {
// DEBUG
// fmt.Printf("Array:%v, Add:%v\n", r, a[i])
r = append(r, add(r, m, a[i], k)...)
}
return r
}
func add(results [][]int, m map[string]bool, v, k int) (out [][]int) {
for _, vr := range results {
// Explore each in index on the arrays from results
for ia := range vr {
// Do not reeplace values already replaced
if vr[ia] > k {
continue
}
// Create copy of array in results (don't want to modify it)
s := append([]int{}, vr[:]...)
s1 := Slice{}
// Looks like I can't mix slice... and single values
s1 = append(s1, s[:ia]...)
s1 = append(s1, v)
s1 = append(s1, s[ia+1:]...)
// Sort elements to discard duplicates
sort.Sort(s1)
// Convert the array to an string to use as a key in a map
ss := fmt.Sprintf("%v", s1)
// Is this array in the map already?
_, ok := m[ss]
if !ok {
out = append(out, s1)
m[ss] = true
}
// DEBUG
// fmt.Printf("New array:%v, Results:%v\n", s1, out)
}
}
return out
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment