组合

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合

示例， n=4， k=2

递归回溯，剪枝

再递归遍历的时候，从1开始，进行组合，1用过之后，下一层遍历则排除1,234进行递归，手动控制递归范围，进行剪枝

func combine(n int, k int) [][]int {
    res := [][]int{}
    if n < k {
        return res
    }
    var handle func(start int, path []int)
    handle = func(start int, path []int) {
        // 得到结果的长度，加入结果，加入后进行回溯
        if len(path) == k {
        	// 后续会修改path，需要拷贝
            tmp := make([]int, len(path))
            copy(tmp, path)
            res = append(res, tmp)
            return
        }
        for i := start; i <= n; i++ {
            // 1加入
            path = append(path, i)
            // 从2开始，判断是否到回溯条件，如果符合，加入最终结果
            handle(i+1, path)
            // 去掉最后一位，继续递归。2完了3
            path = path[:len(path) - 1]
        }

    }
    handle(1, []int{})
    return res
}

空间复杂度O(n)
时间复杂度O(
(k
n)×k)