package combinations

// 77. 组合
// https://leetcode-cn.com/problems/combinations/

var res [][]int

func combine(n int, k int) [][]int {
	res = make([][]int, 0)
	tmp := []int{}
	dfs(n, k, 1, tmp)
	return res
}

func dfs(n, k, i int, tmp []int) {
	if len(tmp) == k {
		res = append(res, append([]int{}, tmp...))
		return
	}

	for s := i; s <= n-(k-len(tmp))+1; s++ {
		tmp = append(tmp, s)
		dfs(n, k, s+1, tmp)
		tmp = tmp[:len(tmp)-1]
	}
	return
}