算法练习：四大算法设计思想之三——回溯算法(Backtracking)

[ShannonChenCHN]

题目列表

• 0-1背包问题⭐️
• 排列、组合、子集相关问题
  • 46. 全排列（难度中等）⭐️
  • 剑指 Offer 38. 字符串的排列（难度中等）
• 游戏问题
  • N 皇后问题 ⭐️
    • 51. N 皇后（难度困难）
    • 52. N皇后 II（难度困难）
  • 37. 解数独（难度困难）⭐️
• 字符串中的回溯问题
  • 10. 正则表达式匹配（难度困难）⭐️
  • 22. 括号生成（难度中等）
• Flood Fill
  • 733. 图像渲染
  • 79. 单词搜索（该题同剑指 Offer 12. 矩阵中的路径）（难度中等）⭐️
  • 剑指 Offer 13. 机器人的运动范围
• 93. 复原 IP 地址

总结

• 回溯算法入门级详解 + 练习（持续更新）
• A general approach to backtracking questions in Java (Subsets, Permutations, Combination Sum, Palindrome Partioning)
• 回溯的时候，要记得在每次递归调用的更深层次函数返回时，需要恢复之前更新的状态
• 每次遇到问题时，先试试能不能用暴力穷举法求解，如果能的话一般可以用回溯解决

[ShannonChenCHN]

理论知识：回溯算法(Backtracking)

1. 什么是回溯算法

回溯法：一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化抛弃该解，即回溯并且再次尝试。

深度优先搜索算法利用的是回溯算法思想。这个算法思想非常简单，但是应用却非常广泛。它除了用来指导像深度优先搜索这种经典的算法设计之外，还可以用在很多实际的软件开发场景中，比如正则表达式匹配、编译原理中的语法分析等。

笼统地讲，回溯算法很多时候都应用在“搜索”这类问题上。不过这里说的搜索指的是，在一组可能的解中，搜索满足期望的解。

回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。

2. 回溯算法适合解决哪一类的问题

很多经典的数学问题都可以用回溯算法解决，比如：

• 数独
• 八皇后⭐️
• 0-1 背包⭐️
• 图的着色
• 旅行商问题
• 全排列
• 正则表达式⭐️

3. 小结

回溯算法的思想非常简单，大部分情况下，都是用来解决广义的搜索问题，也就是，从一组可能的解中，选择出一个满足要求的解。回溯算法非常适合用递归来实现，在实现的过程中，剪枝操作是提高回溯效率的一种技巧。利用剪枝，我们并不需要穷举搜索所有的情况，从而提高搜索效率。

参考

• 极客时间专栏：数据结构和算法之美
• 极客时间专栏：算法通关面试40讲

[ShannonChenCHN]

51. N 皇后（难度困难）

2021.04.24 07:00 pm ~ 11:00 pm

皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

参考题解：

• https://leetcode-cn.com/problems/n-queens/solution/nhuang-hou-by-leetcode-solution/
• https://time.geekbang.org/course/detail/100019701-67639

解法一：暴力枚举法

枚举出将 N 个皇后放置在 N×N 的棋盘上的所有可能的情况，并对每一种情况判断是否满足皇后彼此之间不相互攻击。暴力枚举的时间复杂度是非常高的，因此必须利用限制条件加以优化。

解法二：回溯法

根据题目要求，我们可以发现这样的规律，每个皇后必须位于不同行和不同列，因此将 N 个皇后放置在 N×N 的棋盘上，一定是每一行有且仅有一个皇后，每一列有且仅有一个皇后，且任何两个皇后都不能在同一条斜线上。基于上述发现，可以通过回溯的方式寻找可能的解。

具体思路：使用一个数组记录每行放置的皇后的列下标，依次在每一行放置一个皇后。每次新放置的皇后不能和任何一个已经放置的皇后在同一列以及同一条斜线上，并更新数组中的当前行的皇后列下标。当 N 个皇后都放置完毕，则找到一个可能的解。当找到一个可能的解之后，将数组转换成表示棋盘状态的列表，并将该棋盘状态的列表加入返回列表。

在回溯的过程中，我们需要判断当前位置所在的列和两条斜线上是否已经有皇后，官方题解中给出了两种方式：基于集合和基于位运算。这里我们选择集合的方式来处理，使用三个集合 columns、diagonals1 和 diagonals2 分别记录每一列以及两条斜线上是否有皇后。

那么我们如何记录两条斜线？
仔细分析可以发现，从左上到右下方向，同一条斜线上的每个位置的『列下标与行下标之差』（或者行下标与列下标之差）是一样的，例如 (0,0) 和 (3,3) 在同一条方向一的斜线上。因此使用『列下标与行下标之差』即可明确表示每一条方向一的斜线。
同理，从右上到左下方向，同一条斜线上的每个位置满足『行下标与列下标之和』相等，例如 (3,0) 和 (1,2) 在同一条方向二的斜线上。因此使用『行下标与列下标之和』即可明确表示每一条方向二的斜线。

以 n=4 为例，从第 0 行开始，以 row=0, column = 0 为起点开始回溯：

...
...
...

以 row=0, column = 0 为起点的回溯失败后，再从 row=0, column = 1 开始继续”搜索“，得到了一个解：

时间复杂度：O(n!)
空间复杂度：O(n)。空间复杂度主要取决于递归调用层数、记录每行放置的皇后的列下标的数组以及三个集合，递归调用层数不会超过 n，数组的长度为 n，每个集合的元素个数都不会超过 n。

class Solution {
    var solutions: [[String]] = [[String]]()
    var queenPositions: [Int] = [Int]() // queen 在每一行中的位置
    var columns: [Int] = [Int]()
    var diagonals1: [Int] = [Int]()
    var diagonals2: [Int] = [Int]()
    var n: Int = 1 // 皇后数量

    func solveNQueens(_ n: Int) -> [[String]] {
        self.n = n
        nextRow(0) // 从第 0 行开始
        return solutions
    }

    func nextRow(_ rowIndex: Int) {
        guard rowIndex < n else {
            solutions.append(generateBoard())
            return 
        }

        for columnIndex in 0..<n {
            // 是否同列
            if columns.contains(columnIndex) {
                continue
            }

            // 是否同斜线（撇）
            if diagonals1.contains(columnIndex+rowIndex) {
                continue
            }

            // 是否同斜线（捺）
            if diagonals2.contains(columnIndex-rowIndex) {
                continue
            }
            
            // 放置棋子后更新状态
            queenPositions.append(columnIndex)
            columns.append(columnIndex)
            diagonals1.append(columnIndex+rowIndex)
            diagonals2.append(columnIndex-rowIndex)

            nextRow(rowIndex+1)

            // 恢复状态
            queenPositions.removeLast()
            columns.removeLast()
            diagonals1.removeLast()
            diagonals2.removeLast()
        }
    }

    /// 生成每一轮的结果
    func generateBoard() -> [String] {
        var board: [String] = [String]()
        for rowIndex in 0..<n {
            var rowData: [Character] = [Character](repeating: ".", count: n)
            let columnIndex = queenPositions[rowIndex]
            rowData[columnIndex] = "Q"
            board.append(String(rowData))
        }
        return board
    }
}

解法三：利用位运算进一步优化

详见位运算练习题

[ShannonChenCHN]

36. 有效的数独（难度中等）

注：这一题跟回溯关系不大，不过做 37. 解数独 之前需要做一下这道题。

2021.04.27 08:00 am ~ 09:00 am

参考题解：

• https://leetcode-cn.com/problems/valid-sudoku/solution/you-xiao-de-shu-du-by-leetcode/

解法：一次迭代+哈希表

思路：
一行一行遍历，验证：

• 当前所在行中没有重复的数字。
• 当前所在列中没有重复的数字。
• 当前所在的 3 x 3 子数独内没有重复的数字。

如果出现重复，则返回 false，没有则记录此值并继续遍历。最后返回 true。

两个关键点：

1. 如何检查当前所在的行和列中没有重复项？
   使用 rows<Set> 和 columns<Set> 两个数组分别来记录每一行和每一列出现过的数字，这两个数组大小都为 9。

2. 如何检查当前所在子数独中没有重复项？
   如图 1 所示，我们把大数独分成了 9 个子数独，并使用 boxes<Set> 数组来记录每个子数独中出现过的数字，大小为 9，分别对应子数独 0~8。

本题最最关键的是，子数独索引 boxIndex 和 row 与 column 的对应关系怎么计算呢？
通过观察可以发现，最左侧的子数独索引分别是 0, 3, 6，也就是 3 的倍数，后面两列只是基于第一列的递增。然后我们把每一个小格子的坐标都除以 3，发现可以得到这样的 9 个子数独索引：

[(0, 0), (0, 1), (0, 2)],
[(1, 0), (1, 1), (1, 2)],
[(2, 0), (1, 1), (2, 2)]

综上，子数独索引 boxIndex 和 row 与 column 的对应关系：

boxIndex = (row / 3) * 3 + column / 3

注：当然，为了降低计算 boxIndex 的复杂度，这里的 boxes<Set> 也可以改成二维数组boxes[i][j]<Set>(比如37. 解数独)，整个大数独分成了 3x3 个小数独，坐标如下：

[(0, 0), (0, 1), (0, 2)],
[(1, 0), (1, 1), (1, 2)],
[(2, 0), (1, 1), (2, 2)]

时间复杂度：O(1)。因为我们只对 9x9 个单元格进行了一次迭代。
空间复杂度：O(1)。因为我们只申请了 3 个大小为 9 的数组，并每个数组中的 set 最多也只会记录 9 个数字。

class Solution {
    func isValidSudoku(_ board: [[Character]]) -> Bool {
        var rows = [Set<Character>](repeating: Set<Character>(), count: 9)
        var columns = [Set<Character>](repeating: Set<Character>(), count: 9)
        var boxes = [Set<Character>](repeating: Set<Character>(), count: 9)

        for rowIndex in 0..<9 {
            let boardRow = board[rowIndex]
            for columnIndex in 0..<9 {
                let item = boardRow[columnIndex]
                if item == "." {
                    continue
                }

                let boxIndex = (rowIndex / 3) * 3 + columnIndex / 3
                
                if  rows[rowIndex].contains(item) || 
                    columns[columnIndex].contains(item) ||
                    boxes[boxIndex].contains(item) {
                    return false
                }

                rows[rowIndex].insert(item)
                columns[columnIndex].insert(item)
                boxes[boxIndex].insert(item)
            }
        }
        return true
    }
}

[ShannonChenCHN]

37. 解数独（难度困难）

2021.05.01 10:30 pm ~ 12:30 pm

参考题解：

• https://leetcode-cn.com/problems/sudoku-solver/solution/jie-shu-du-by-leetcode-solution/

解法一：数组+回溯

我们可以考虑按照「行优先」的顺序依次枚举每一个空白格中填的数字，通过递归 + 回溯的方法枚举所有可能的填法。当递归到最后一个空白格后，如果仍然没有冲突，说明我们找到了答案；在递归的过程中，如果当前的空白格不能填下任何一个数字，那么就进行回溯。

几个变量：

• emptyCells: [(Int, Int)] 记录所有空白格的位置
• rows: [[Bool]]：记录每一行中1~9各数字是否出现过
• columns: [[Bool]]：记录每一列中1~9各数字是否出现过
• boxes: [[[Bool]]]：记录每一个子区块中1~9各数字是否出现过

递归：

• 终止条件：最后一个空白格也被填了
• 重复内容：递归每一次执行实际上是每一个空白格的填写过程，也就是依次枚举 1~9 这 9 个数字，先判断能不能填，如果能填就继续下一个空白格，不能填就什么都不干，回到上一步。另外需要注意的是，在填最后一个空白格时，如果找到了合适的数字，就不要再尝试剩下的数字了。

时间复杂度：这里的时间复杂度很大程度取决于给定的输入数据，而我们很难找到一个非常精确的渐进紧界。因此这里只给出一个较为宽松的渐进复杂度上界 O(9^81)，即最多有 9×9 个空白格，每个格子可以填 [1, 9] 中的任意整数。
空间复杂度：也决于给定的输入数据，最坏的情况是

class Solution {
    var emptyCells: [(Int, Int)] // 记录所有空白格的位置
    var rows: [[Bool]]    // 记录每一行中1~9各数字是否出现过
    var columns: [[Bool]] // 记录每一列中1~9各数字是否出现过
    var boxes: [[[Bool]]] // 记录每一个子区块中1~9各数字是否出现过
    var isCompleted: Bool // 是否已经完成

    init() {
        emptyCells = [(Int, Int)]()
        rows = [[Bool]](repeating: [Bool](repeating: false, count: 10), count: 9)
        columns = [[Bool]](repeating: [Bool](repeating: false, count: 10), count: 9)
        boxes = [[[Bool]]](repeating: [[Bool]](repeating: [Bool](repeating: false, count: 10), count: 3), count: 3)
        isCompleted = false
    }

    func solveSudoku(_ board: inout [[Character]]) {
        for row in 0..<9 {
            for column in 0..<9 {
                let char: Character = board[row][column]
                if char == "." { // 记录所有空白格的位置
                    emptyCells.append((row, column)) 
                } else {
                    // 记录每一行、列、子区块的数字状态
                    if let digit = Int(String(char)) {
                        rows[row][digit] = true
                        columns[column][digit] = true
                        boxes[row/3][column/3][digit] = true
                    }
                }
            }
        }

        // 开始遍历空白格
        dfs(&board, 0)
    }

    func dfs(_ board: inout [[Character]], _ emptyCellIndex: Int) {
        guard emptyCellIndex < emptyCells.count else {
            isCompleted = true
            return
        }

        let row = emptyCells[emptyCellIndex].0
        let column = emptyCells[emptyCellIndex].1

        for digit in 1...9 {
            if isCompleted { // 如果已经都填满了，就不需要再继续尝试了
                return
            }
            
            if !rows[row][digit] && 
            !columns[column][digit] && 
            !boxes[row/3][column/3][digit] {
                rows[row][digit] = true
                columns[column][digit] = true
                boxes[row/3][column/3][digit] = true
                board[row][column] = Character(String(digit))
                
                dfs(&board, emptyCellIndex+1)

                rows[row][digit] = false
                columns[column][digit] = false
                boxes[row/3][column/3][digit] = false
            }
        }
    }
}

解法二：位运算+回溯

TODO

[ShannonChenCHN]

46. 全排列（难度中等）

2021.05.01 02:00 pm ~ 03:00 pm

解法一

我们可以把这个问题看作是有 n 个排列成一行的空格，我们需要从左往右依此填入题目给定的 n 个数字，每个数字只能使用一次。那么很直接的可以想到一种穷举的算法，即从左往右每一个位置都依此尝试填入一个数，看能不能填完这 n 个空格。

class Solution {
    var result: [[Int]] = [[Int]]()

    func permute(_ nums: [Int]) -> [[Int]] {
        var output = [Int]()
        dfs(nums, &output)
        return result
    }

    func dfs(_ nums: [Int], _ output: inout [Int]) {
        guard output.count < nums.count else {
            result.append(output)
            return
        }

        for num in nums {
            if output.contains(num) {
                continue
            }
            output.append(num)
            dfs(nums, &output)
            output.removeLast()
        }
    }
}

解法二

参考题解：https://leetcode-cn.com/problems/permutations/solution/quan-pai-lie-by-leetcode-solution-2/

将题目给定的 n 个数的数组 nums 划分成左右两个部分，左边的表示已经填过的数，右边表示待填的数，我们在回溯的时候只要动态维护这个数组即可。

class Solution {
    var result: [[Int]] = [[Int]]()

    func permute(_ nums: [Int]) -> [[Int]] {
        var nums = nums
        dfs(&nums, 0)
        return result
    }

    func dfs(_ output: inout [Int], _ separatorIndex: Int) {
        guard separatorIndex < output.count else {
            result.append(output)
            return
        }

        for i in separatorIndex..<output.count {
            output.swapAt(separatorIndex, i)
            dfs(&output, separatorIndex+1)
            output.swapAt(separatorIndex, i)
        }
    }
}

[ShannonChenCHN]

79. 单词搜索（难度中等）

2021.05.01 08:15 pm ~ 09:30 pm

解法一

参考图解：https://leetcode-cn.com/problems/word-search/solution/zai-er-wei-ping-mian-shang-shi-yong-hui-su-fa-pyth/
参考题解：

• https://leetcode-cn.com/problems/word-search/solution/dan-ci-sou-suo-by-leetcode-solution/
• https://leetcode.com/problems/word-search/discuss/346841/Swift-Solution-Clean-and-Easy-Understand

结合图解，大概思路如下：
从第一个格子开始，一行一行地遍历，并以当前格子的字母为首字母进行匹配。匹配逻辑为递归操作，匹配时先看当前字母是否一致，如果一致则接着往周边四个方向(需要排除掉已经访问过的)继续匹配下一个字母，不一致则返回前一个字母的匹配换另一个方向继续匹配，也就是回溯。

几个变量：

• visited: [[Bool]]：记录某个位置是否已经访问过

递归：

• 终止条件
  • 如果当前位置的字母不匹配直接返回 false
  • 如果目标字符串的所有字母都已经匹配成功了，直接返回 true
  • 如果递归调用的更深层次返回结果为 true，也就是说后面的字符串都匹配成功了，直接返回 true
• 重复内容
  • 更新 visited 变量
  • 遍历四个方向： i+1, i-1, j+1, j-1，递归调用继续匹配下一个字母

class Solution {
    var visited: [[Bool]] = [[Bool]]()

    func exist(_ board: [[Character]], _ word: String) -> Bool {
        var board = board
        var chars = Array(word)
        let rowCount = board.count
        let columnCount = board[0].count
        visited = [[Bool]](repeating: [Bool](repeating: false, count: columnCount), count: rowCount)
        for i in 0..<rowCount {
            for j in 0..<columnCount {
                if board[i][j] == chars[0] && 
                   isMatch(&board, i, j, &chars, 0) {
                    return true
                }
            }
        }
        return false
    }

    func isMatch(_ board: inout [[Character]], _ x: Int, _ y: Int, _ word: inout [Character], _ idx: Int) -> Bool {
        // 所有的字母都匹配成功了
        guard idx < word.count else {
            return true
        }

        // 防止出界
        guard x >= 0 && x < board.count && 
            y >= 0 && y < board[0].count else { 
            return false
        }

        // 已经访问过
        guard !visited[x][y] else { 
            return false
        }

        // 当前字母必须要匹配
        guard board[x][y] == word[idx] else {
            return false
        }
        
        visited[x][y] = true

        // 继续匹配后面剩下的字符
        let isSuffixMatched = isMatch(&board, x, y-1, &word, idx+1) || 
        isMatch(&board, x, y+1, &word, idx+1) ||
        isMatch(&board, x-1, y, &word, idx+1) ||
        isMatch(&board, x+1, y, &word, idx+1)
        
        // 回溯时恢复状态
        visited[x][y] = false

        return isSuffixMatched
    }
}

[ShannonChenCHN]

22. 括号生成

[ShannonChenCHN]

0-1背包问题