Combinations can be printed using the following recursive code (inspired from Rosetta)
I thought it would be easy to store the intermediate results in an []int or the set of combination in an [][]int. But, because the function is recursive, it is not so easy than replacing the
fmt.Println(s)
by a
return s
with a minor modification of the function output for example. I also tried to feed a pointer like
p *[][]int
with the variable "s" inside the recursive function, but I failed :-/
I think it is a general problem with recursive functions so if you have some advises to solve this problem it will help me a lot !
Many thanks in advance ! ;)
package main
import (
"fmt"
)
func main() {
comb(5, 3)
}
func comb(n, m int) {
s := make([]int, m)
last := m - 1
var rc func(int, int)
rc = func(i, next int) {
for j := next; j < n; j++ {
s[i] = j
if i == last {
fmt.Println(s)
} else {
rc(i+1, j+1)
}
}
return
}
rc(0, 0)
}
Seems to me that s is being reused by each rc call so you just need to ensure that when storing s into an [][]int you store its copy, so as to not overwrite its contents during the next iteration.
To copy a slice you can use append like this:
scopy := append([]int{}, s...)
https://play.golang.org/p/lggy5JFL0Z
package main
import (
"fmt"
)
func main() {
out := comb(5, 3)
fmt.Println(out)
}
func comb(n, m int) (out [][]int) {
s := make([]int, m)
last := m - 1
var rc func(int, int)
rc = func(i, next int) {
for j := next; j < n; j++ {
s[i] = j
if i == last {
out = append(out, append([]int{}, s...))
} else {
rc(i+1, j+1)
}
}
return
}
rc(0, 0)
return out
}