77.组合

leetcode

递归实现：

func combine(n int, k int) [][]int {
    curr := []int{}
    result := [][]int{}

    var dfs func(int)
    dfs = func(i int) {
        //如果剩下的数都取，还不够k，就剪枝
        if len(curr) + n - i + 1 < k {
            return
        }

        if len(curr) == k {
            result = append(result, append([]int{}, curr...))
            return
        }

        curr = append(curr, i)
        dfs(i + 1)

        curr = curr[:len(curr) - 1]
        dfs(i + 1)
    }

    dfs(1)
    return result
}