如何在GO中的切片中存储递归获得的组合？

Question

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)
}

Answer 1

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
}