[代码随想录]Day21-回溯算法part01

题目：77. 组合

思路：

回溯就是dfs的一个特殊情况也就是递归的一种情况，值得注意的一点：

要记得深拷贝，不然最后全是空

代码：

var res  [][]int
var path []int
func combine(n int, k int) [][]int {
    res = [][]int{}
    path = make([]int, 0,k)
    Combine(n, 1, k, 0) 
    return res
}
func Combine(n, start, k, lens int) {
    if lens == k {
        x := append([]int{}, path...)
        res = append(res, x)
        return
    }
    for i := start; i <= n; i++ {
        path = append(path, i)
        Combine(n, i+1, k, lens+1) // 递归
        path = path[:lens] // 回溯
    }
}

参考：

代码随想录