从字节面试题中学回溯

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

▼
text
复制代码
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

▼
text
复制代码
输入：s = "a"
输出：[["a"]]

提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

回溯

▼
java
复制代码
class Solution {
    List<List<String>> res = new LinkedList<>();
    List<String> track = new LinkedList<>();

    public List<List<String>> partition(String s) {
        backtrack(s, 0);
        return res;
    }

    void backtrack(String s, int start) {
        if (start == s.length()) {
            // base case
            // 越界，即整个 s 被成功分割为若干个回文子串，记下答案
            res.add(new ArrayList<String>(track));
        }
        
        // for 和 if 是用来检查字符串是否应该被放到track列表里的
        for (int i = start; i < s.length(); i++) {
            if (!isPalindrome(s, start, i)) {
                // s[start..i] 不是回文串，不能分割，继续检查s[start, i+1]
                continue;
            }
            
            // s[start..i] 是一个回文串，可以进行分割
            // 做选择，把 s[start..i] 放入路径列表中
            track.addLast(s.substring(start, i + 1));
            // 进入回溯树的下一层，继续切分 s[i+1..]
            backtrack(s, i + 1);
            // 撤销选择
            track.removeLast();
        }
    }

    // 用双指针技巧判断 s[lo..hi] 是否是一个回文串
    boolean isPalindrome(String s, int lo, int hi) {
        while (lo < hi) {
            if (s.charAt(lo) != s.charAt(hi)) {
                return false;
            }
            lo++;
            hi--;
        }
        return true;
    }
}

• 时间复杂度：O(N*2^N)；这里 N 为输入字符串的长度，每一个位置可拆分，也可不拆分，尝试是否可以拆分的时间复杂度为 O(2^N)，判断每一个子串是否是回文子串，时间复杂度为 O(N)；
• 空间复杂度：
  • 如果不计算保存结果的空间，空间复杂度为 O(N)，递归调用栈的高度为 N；
  • 如果计算保存答案需要空间 2^N*N，这里 2^N 为保守估计，实际情况不会这么多。空间复杂度为 O(2^N*N)。

90. 子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

▼
text
复制代码
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

▼
text
复制代码
输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

回溯

▼
java
复制代码
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    List<Integer> track = new LinkedList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // 先排序，让相同的元素靠在一起
        Arrays.sort(nums);
        backtrack(nums, 0);
        return res;
    }

    void backtrack(int[] nums, int start) {
        // 前序位置，每个节点的值都是一个子集。重点。
        res.add(new LinkedList<>(track));

        for (int i = start; i < nums.length; i++) {
            // 剪枝，值相同的相邻树枝，只遍历第一条。重点。
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            
            track.addLast(nums[i]);
            backtrack(nums, i + 1);
            track.removeLast();
        }
    }
}

• 可能的子集数量为 2^n，对于每一个子集，程序都会执行一系列操作，其中包括子集的构造和检查，平均情况下，每个子集的长度是 O(n)。回溯搜索的总复杂度可以近似表示为 O(n*2^n)，这是因为回溯会对每个可能的子集进行构建和复制。
• new LinkedList<>(track) 这行代码会创建一个新的 LinkedList 实例，并将当前 track 中的所有元素复制到新列表中。复制 track 的所有元素的时间复杂度是 O(k)，其中 k 是当前 track 的长度。res.add(...) 是将新子集加入到结果列表 res 中，这个操作本身是常数时间 O(1)，因为 LinkedList 的尾插入操作时间复杂度为 O(1)。在回溯生成子集的过程中，track 的长度会随着递归的深度变化。最坏情况下，track 可以达到最大长度，即 n（输入数组的长度）。因此，复制 track 的操作在最坏情况下是 O(n)。因此如果不考虑结果链表res，空间复杂度是 O(n)。res的空间复杂度是O(n*2^n)。

491. 非递减子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：

▼
text
复制代码
输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2：

▼
text
复制代码
输入：nums = [4,4,3,2,1]
输出：[[4,4]]

提示：

• 1 <= nums.length <= 15
• -100 <= nums[i] <= 100

回溯

▼
java
复制代码
class Solution {
    public List<List<Integer>> findSubsequences(int[] nums) {
        if (nums.length == 0) {
            return res;
        }
        
        backtrack(nums, 0);
        return res;
    }

    List<List<Integer>> res = new LinkedList<>();
    // 记录回溯的路径
    List<Integer> track = new LinkedList<>();

    // 回溯算法主函数
    void backtrack(int[] nums, int start) {
        if (track.size() >= 2) {
            // 找到一个合法答案，不能返回，还要继续找。重点。
            res.add(new LinkedList<>(track));
        }
        
        // 用哈希集合防止重复选择相同元素，横向作用
        Set<Integer> used = new HashSet<>();
        // 回溯算法标准框架
        for (int i = start; i < nums.length; i++) {
            // 剪枝，保证集合中元素都是递增顺序。重点。
            if (!track.isEmpty() && track.getLast() > nums[i]) {
                continue;
            }
            // 剪枝，确保递增，即不要重复使用相同的元素，
            if (used.contains(nums[i])) {
                continue;
            }
            
            // 选择 nums[i]
            used.add(nums[i]);
            track.add(nums[i]);
            // 递归遍历下一层回溯树
            backtrack(nums, i + 1);
            // 撤销选择 nums[i]
            track.removeLast();
            // 这里不能写used.remove(nums[i])，因为used是当前递归层的状态，不是全局状态。
        }
    }
}

• 时间复杂度为 O(n*2^n)。这里 n 是用于每一层循环的复杂度估算，2^n 是由于每个元素都有加入或不加入子序列的选择。HashSet 的操作（add 和 contains）都是 O(1) 的时间复杂度。
• 递归的深度最多为 n，因此递归栈的空间复杂度是 O(n)。存储结果的空间复杂度取决于生成的子序列数量和长度，这在最坏情况下接近 O(2^n*n)。

47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

▼
text
复制代码
输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

▼
text
复制代码
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

回溯

▼
java
复制代码
class Solution {
    List<List<Integer>> res = new LinkedList<>(); // 结果列表
    List<Integer> track = new LinkedList<>(); // 用于存储当前的排列内容
    boolean[] used; // 标记数组，用来记录nums中的元素是否已经被使用

    public List<List<Integer>> permuteUnique(int[] nums) {
        // 先对数组进行排序，这样相同的数字就会被排列在一起，便于后续剪枝
        Arrays.sort(nums);
        used = new boolean[nums.length];
        
        backtrack(nums);
        return res;
    }

    void backtrack(int[] nums) {
        // 如果当前排列的长度等于nums的长度，说明找到了一个完整的排列。排列的长度是一样的。
        if (track.size() == nums.length) {
            res.add(new LinkedList(track)); // 将当前排列添加到结果列表中
            return;
        }

        // 从头开始遍历
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) { // 纵向比较进行剪枝
                continue; // 如果nums[i]已经在本路径中被使用过，则跳过
            }
            // 因为数组中有重复元素，所以需要横向比较进行剪枝，以避免产生重复的排列。used是纵向的，即跨递归的，方法二中的prevNum是横向的。
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                // 如果当前数字和前一个数字相同，且前一个数字还未被使用过，则跳过
                // 这是因为这种情况会产生和前一个数字相同的排列，导致产生相同的排列
                continue;
            }
            
            track.add(nums[i]); // 将nums[i]添加到当前排列中
            used[i] = true; // 标记nums[i]已经被使用
            backtrack(nums); // 递归调用，继续填充排列的下一个数字
            track.removeLast(); // 回溯，从当前排列中移除nums[i]
            used[i] = false; // 取消对nums[i]的使用标记
        }
    }
}

• 总共有n!种排列，每个排列都需要被复制到res中，这个操作的时间复杂度是O(n)，因此总的时间复杂度是O(n*n!)
• 记忆数组O(n)，递归栈O(n)。

回溯

▼
java
复制代码
class Solution {
    List<List<Integer>> res = new LinkedList<>(); // 结果列表
    LinkedList<Integer> track = new LinkedList<>(); // 用于存储当前的排列内容
    boolean[] used; // 标记数组，用来记录nums中的元素是否已经被使用

    public List<List<Integer>> permuteUnique(int[] nums) {
        // 先对数组进行排序，这样相同的数字就会被排列在一起，便于后续剪枝
        Arrays.sort(nums);
        used = new boolean[nums.length];
        backtrack(nums, track);
        return res;
    }

    void backtrack(int[] nums, LinkedList<Integer> track) {
        if (track.size() == nums.length) {
            res.add(new LinkedList(track));
            return;
        }

        // 利用prevNum变量记录之前树枝上元素的值
        // 题目说 -10 <= nums[i] <= 10，所以初始化为特殊值
        // used是全局记忆数组，prevNum是每层递归中的记忆变量
        int prevNum = -666;
        for (int i = 0; i < nums.length; i++) {
            // 排除不合法的选择
            if (used[i]) {
                continue;
            }
            // 注意prevNum是每层递归中的变量，不会跨递归，因此prevNum是本轮递归中的前一个数，即横向的数，不是track中的上一个选择。
            if (nums[i] == prevNum) {
                continue;
            }

            track.add(nums[i]);
            used[i] = true;
            // 记录这条树枝上的值
            prevNum = nums[i];

            backtrack(nums, track);

            track.removeLast();
            used[i] = false;
        }
    }
}

37. 解数独

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1：

▼
text
复制代码
输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示： 

提示：

• board.length == 9
• board[i].length == 9
• board[i][j] 是一位数字或者 '.'
• 题目数据 保证 输入数独仅有一个解

回溯

▼
java
复制代码
class Solution {
    public void solveSudoku(char[][] board) {
        backtrack(board, 0, 0); // 开始从 (0, 0) 位置开始进行回溯
    }

    boolean backtrack(char[][] board, int i, int j) {
        int m = 9, n = 9; // 数独的大小固定为 9x9
        if (j == n) {
            // 如果穷举到最后一列的话，就换到下一行重新开始。重点。
            return backtrack(board, i + 1, 0);
        }
        if (i == m) {
            // 如果穷举到最后一行，说明找到一个可行解。重点。
            return true;
        }

        if (board[i][j] != '.') {
            // 如果当前位置有预设数字，不用我们穷举，直接跳到下一个位置。重点。
            return backtrack(board, i, j + 1);
        }

        // 尝试填入数字 1 到 9
        for (char ch = '1'; ch <= '9'; ch++) {
            // 如果遇到不合法的数字，跳过
            if (!isValid(board, i, j, ch))
                continue;

            board[i][j] = ch; // 做选择：填入数字 ch
            // 判断 3x3 方框是否存在重复。重点。r/3是从上往下数第几个方块，每一个方块都有三行，所以r/3就是第几行。
            if (backtrack(board, i, j + 1)) {
                return true;
            }
            board[i][j] = '.'; // 撤销选择：恢复为空格
        }
        
        // 穷举完 1 到 9，依然没有找到可行解，返回 false 表示此路不通
        return false;
    }

    // 判断 board[r][c] 是否可以填入字符 n
    boolean isValid(char[][] board, int r, int c, char n) {
        for (int i = 0; i < 9; i++) {
            // 判断行是否存在重复
            if (board[r][i] == n) return false;
            // 判断列是否存在重复
            if (board[i][c] == n) return false;
            // 判断 3x3 方框是否存在重复。重点。
            if (board[(r / 3) * 3 + i / 3][(c / 3) * 3 + i % 3] == n)
                return false;
        }
        return true; // 如果以上条件都不满足，说明可以填入字符 n
    }
}

• 在最坏情况下，每个空格都需要穷举 9 个数字。因此最差情况下，时间复杂度是 O(9^N)。
• 空间复杂度主要由递归调用栈的深度决定：在最坏情况下，递归的最大深度为 N，即数独中所有空格的数量。每次递归调用会使用常数级别的空间（例如局部变量和参数），所以空间复杂度为 O(N)。

解释一下判断 3x3 方框是否存在重复的代码。

假设我们在一个数独棋盘上操作，当前的位置是 (r, c)，比如说位置 (4, 4)，我们要检查数字 5 是否可以放在这个位置。

首先，我们需要找到 (4, 4) 所在的 3x3 小方框：

▼
text
复制代码
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . 5 . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+

我们看到 (4, 4) 在棋盘的中心，位于中间的 3x3 小方框中。

• (r / 3) 表示当前行 r 所在的 3x3 小方框的行索引。对于 r = 4，计算 (4 / 3) = 1，表示当前行位于第二个 3x3 小方框的行。
• (c / 3) 表示当前列 c 所在的 3x3 小方框的列索引。对于 c = 4，计算 (4 / 3) = 1，表示当前列位于第二个 3x3 小方框的列。

所以，当前 3x3 小方框的左上角坐标是 (1 * 3, 1 * 3)，即 (3, 3)。

我们需要遍历这个 3x3 小方框的所有位置，检查是否有重复数字 n。遍历的索引用 i 从 0 到 8，每个 i 对应小方框中的一个位置。

• i / 3 是当前元素在 3x3 小方框中的行索引。例如，当 i 取 0, 1, 2 时，对应 3x3 小方框的第一行，i / 3 = 0；当 i 取 3, 4, 5 时，对应 3x3 小方框的第二行，i / 3 = 1；当 i 取 6, 7, 8 时，对应 3x3 小方框的第三行，i / 3 = 2。
• i % 3 是当前元素在 3x3 小方框中的列索引。例如，当 i 取 0, 3, 6 时，对应 3x3 小方框的第一列，i % 3 = 0；当 i 取 1, 4, 7 时，对应 3x3 小方框的第二列，i % 3 = 1；当 i 取 2, 5, 8 时，对应 3x3 小方框的第三列，i % 3 = 2。