leetcode-go/medium/77.go

package main

import (
	"fmt"
)

func combinIter(n int, k int, last []int, res *[][]int) {
	solution := make([]int, len(last))
	copy(solution, last)
	if k == 0 {
		*res = append(*res, solution)
		return
	}
	var i int
	if len(solution) != 0 {
		i = solution[len(solution)-1] + 1
	} else {
		i = 1
	}
	for ; i <= n; i++ {
		combinIter(n, k-1, append(solution, i), res)
	}
}

func combineOld(n int, k int) (res [][]int) {
	combinIter(n, k, []int{}, &res)
	return
}

// a cleaner way of recursion
func combine(n int, k int) (res [][]int) {
	// Cnn or C0n
	if n == k || k == 0 {
		row := make([]int, k)
		for i := range row {
			row[i] = i + 1
		}
		return append(res, row)
	}
	// C(k)(n) = C(k-1)(n-1) + C(k)(n-1)
	for _, row := range combine(n-1, k-1) {
		row = append(row, n)
		res = append(res, row)
	}
	res = append(res, combine(n-1, k)...)
	return
}

func main() {
	fmt.Println(combine(4, 2))
	fmt.Println(combine(5, 4))
	fmt.Println(combine(1, 1))
}