回溯套路

回溯的逻辑上应该很好理解，但许久不做题后一想到用回溯，总觉得无法下码，其实是对代码代码结构认识不足。这里整理一下。

回溯是一种暴力方法，在算法中一般要返回所有的组合的时候可以用回溯，如果要返回个数值，应该考虑动态规划等其他方法。

力扣刷题提醒

• 看力扣题最后的提示，数据量不大的时候用暴力！！！（竞赛拼手速）

基本算法模型设计

• 回溯问题是一个遍历问题；
• 在遍历过程中对一个元素有两种处理方式：选择 和 不选择；
• 在选择和不选择之后，都需要考虑下一个节点，所以一定会用到递归；
• 如果用了 for 循环，在不选择（第二次处理）之后，可以通过 for 代替这次递归；
• 一般需要两个容器：选择列表的容器和存放结果的容器；
• 在选择和或不选择之间，常常需要恢复选择列表容器的“选择场景”；
• 由上特性，这两个容器应该是引用传递的、或者全局的、或者使用闭包式。
• 剪枝：如果后面的肯定不符合条件，则结束向后递归。

  剪枝的条件找的全的话也能甩力扣一大波人，有些剪枝条件不好找。

基本模型代码

func backtrace(nums []int) [][]int {
    // 1. init containers: result and temp

    // 2. define and implement dfs
    var dfs func(args ...) // define
    dfs = func(args ...) { // implement
        // 2.1 judge and pruning
        // 2.x judge result and save to []result（根据题意不同位置）

        // 2.2 do choice
        // 2.3 next with choice
        dfs(i + 1)

        // 2.4 recover scenario (do no choice)
        // 2.5 next with no choice
        dfs(i + 1)
    }
    // start call
    dfs(0)

    return result
}

例题

N 个数的全排列

每个节点都发生了取值，但取值的顺序不一样，所以这个递归套路和上方的不太一样了。

func allArrangeN(n int) [][]int {
    nums := make([]int, n)
    for i := 0; i < n; i++ {
        nums[i] = i + 1
    }

    res := make([][]int, 0)
    temp := make([]int, 0, n)

    var dfs func(ns []int)
    dfs = func(ns []int) {
        // pruning
        if len(temp) == n {
            res = append(res, append([]int{}, temp...))
            return
        }
        for i := 0; i < len(ns); i++ {
            // do choice
            temp = append(temp, ns[i])
            // next with do choice
            dfs(append(append([]int{}, ns[:i]...), ns[i+1:]...))
            // recover
            temp = temp[:len(temp)-1]
            // next with no choice
            dfs(append(append([]int{}, ns[:i]...), ns[i+1:]...))
        }
    }
    dfs(nums)
    fmt.Println(res)
    return res
}

// 上述 dfs 可以变成这样，做选择只选第一个元素。看代码会简单一些
// 内存的使用？？？
    dfs = func(ns []int) {
        // pruning
        if len(temp) == n {
            res = append(res, append([]int{}, temp...))
            return
        }
        for i := 0; i < len(ns); i++ {
            ns[0], ns[i] = ns[i], ns[0] // 每次交换到第一个，做选择也只选择第一个
            // do choice
            temp = append(temp, ns[0])
            // next with do choice
            dfs(append([]int(nil), ns[1:]...))
            // recover
            temp = temp[:len(temp)-1]
        }
    }

求 n 个数中所有 k 个元素的组合

给定 n 即表示 [1, n] 的 n 个数。

力扣：77. 组合

func combine(n int, k int) [][]int {
    if n < k {
        return nil
    }
    // 1. init containers: result and temp
    res := make([][]int, 0, n*n)
    temp := make([]int, 0, k)

    // 2. define and implement dfs
    var dfs func(i int)
    dfs = func(i int) {
        // 2.1 pruning
        if i > n || len(temp) > k || len(temp)+n-i+1 < k {
            return
        }

        // 2.2 do choice
        temp = append(temp, i)
        // 2.x add result
        if len(temp) == k {
            res = append(res, append([]int{}, temp...))
        }
        // 2.3 next with choice
        dfs(i + 1)

        // 2.4 recover scenario (do no choice)
        temp = temp[:len(temp)-1]
        // 2.5 next with no choice
        dfs(i + 1)
    }

    dfs(1)

    return res
}

求数组中所有可能子集

子集包含空集，子集内元素不考虑顺序，结果不考虑顺序

力扣：78. 子集

func subsets(nums []int) [][]int {
    // init containers: result and temp
    result := make([][]int, 0)
    result = append(result, []int{}) // 题意：每个数组一定会有一个空
    temp := make([]int, 0, len(nums))

    // define and implement dfs
    var dfs func(i int) // define
    dfs = func(i int) { // implement
        // pruning
        if i >= len(nums) {
            return
        }

        // do choice
        temp = append(temp, nums[i])
        // add result
        result = append(result, append([]int{}, temp...))
        // next with choice
        dfs(i + 1)

        // recover scenario (do no choice)
        temp = temp[:len(temp)-1]
        // next with no choice
        dfs(i + 1)
    }

    dfs(0)

    return result
}

从矩阵中查看单词是否存在

力扣：79. 单词搜索

func exist(board [][]byte, word string) bool {
    if word == "" {
        return true
    }
    if len(board) == 0 || len(board[0]) == 0 {
        return false
    }
    m, n := len(board), len(board[0])

    moves := [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
    used := make(map[[2]int]struct{}, 0)
    result := false

    var dfs func(i int, cur [2]int)
    dfs = func(i int, cur [2]int) {
        // pruning
        if result {
            return
        }
        if _, ok := used[cur]; ok || !validPos(cur, m, n) || board[cur[0]][cur[1]] != word[i] {
            return
        }
        if i == len(word)-1 {
            result = true
            return
        }
        // do choice
        used[cur] = struct{}{}
        // next with do choice
        for _, move := range moves {
            newCur := [2]int{cur[0] + move[0], cur[1] + move[1]}
            dfs(i+1, newCur)
        }
        // recover scenario (do no choice)
        delete(used, cur)
        // next for loop
    }

    for i := 0; i < len(board); i++ {
        for j := 0; j < len(board[0]); j++ {
            // start
            dfs(0, [2]int{i, j})

            // pruning
            if result {
                return result
            }
        }
    }
    return result
}

func validPos(pos [2]int, m, n int) bool {
    if pos[0] < 0 || pos[0] >= m {
        return false
    }
    if pos[1] < 0 || pos[1] >= n {
        return false
    }
    return true
}

只打败了 5% 【捂脸】：执行耗时:696 ms,击败了5.01% 的Go用户，内存消耗:2.1 MB,击败了6.76% 的Go用户。但回溯的思路没问题，而且和官方给出的思路也差不多。

尝试逐步优化：
用和 board 等量的 bool 矩阵替换 used 后：执行耗时:168 ms,击败了8.97% 的Go用户，内存消耗:1.9 MB,击败了62.02% 的Go用户
传递时用 i, j 代替 [2]int{i,j} 后：执行耗时:128 ms,击败了12.74% 的Go用户，内存消耗:1.9 MB,击败了62.02% 的Go用户

直接用官网给出的方法：执行耗时:96 ms,击败了37.84% 的Go用户，内存消耗:1.9 MB,击败了30.39% 的Go用户
不优化了，不过根据上方的优化变动，可以思考下面两点信息（不排除 力扣 对相同代码每次跑的结果不一样）：

• 频繁用 map 增加删除和用固定长度的数组相比，效率不高
• 传数组似乎比只传下标更耗时些

（闲来无事做了这个 check，不一定准确，不要以此为准）

有重复元素的所有子集

• 力扣：90. 子集Ⅱ

func subsetsWithDup(nums []int) [][]int {
    res := make([][]int, 0)
    res = append(res, []int{})
    if len(nums) == 0 {
        return res
    }

    sort.Ints(nums)
    counts := make(map[int]int, len(nums))
    counts[nums[0]]++
    cur := 0
    // 去重、统计 counts
    for i := 1; i < len(nums); i++ {
        counts[nums[i]]++
        if nums[i] != nums[cur] {
            cur++
            nums[cur] = nums[i]
        }
    }
    nums = nums[:cur+1]

    temp := make([]int, 0, len(nums))
    var dfs func(i int)
    dfs = func(i int) {
        if i >= len(nums) {
            return
        }
        elem := nums[i]
        count := counts[elem]

        // do choice
        for c := 1; c <= count; c++ {
            // do N choice
            for k := 0; k < c; k++ {
                temp = append(temp, elem)
            }
            res = append(res, append([]int{}, temp...))
            // next with do N choice
            dfs(i + 1)
            // recover N (do no choice)
            for k := 0; k < c; k++ {
                temp = temp[:len(temp)-1]
            }
        }
        // next with do no choice
        dfs(i + 1) // 注意这里必须在上面的 for 外面，否则会导致多次 do no choice
    }
    dfs(0)
    return res
}

执行结果：执行耗时:0 ms,击败了100.00% 的Go用户，内存消耗:2.4 MB,击败了12.90% 的Go用户

尽可能公平地分桶

5289. 公平分发饼干

func distributeCookies(cookies []int, k int) int {
    buckets := make([]int, k)
    n := len(cookies)
    max := func(a ...int) int {
        m := 0
        for _, i := range a {
            if i > m {
                m = i
            }
        }
        return m
    }
    var dfs func(i int)
    minRes := math.MaxInt
    dfs = func(i int) {
        // pruning
        if i == n {
            if m := max(buckets...); m < minRes {
                minRes = m
            }
            return
        }
        // do choice by buckets
        for j := 0; j < len(buckets); j++ {
            // do choice
            buckets[j] += cookies[i]
            // next with do choice
            dfs(i + 1)
            // recover
            buckets[j] -= cookies[i]
            // next with recover
            // dfs(i + 1) // 因为这个元素必须选一个桶放，如果不选就不能向下递归了，所以这里没有此行
        }
    }
    dfs(0)
    return minRes
}