LeetCode回溯算法全解析：从基础到高级应用

安全风信子

发布于 2025-11-13 14:07:42

1410

文章被收录于专栏：AI SPPECHAI SPPECH

一、回溯算法基础

1.1 回溯算法的基本概念

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

回溯算法通常用递归实现，其基本思想是：

尝试所有可能的选择
对于每个选择，继续尝试剩余的选择
如果当前选择无法得到解，则撤销该选择，回到上一步，尝试其他选择

回溯算法可以看作是一种暴力搜索算法，但它通过剪枝来减少搜索空间，提高效率。

1.2 回溯算法的框架

回溯算法的基本框架可以用以下伪代码表示：

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

在这个框架中：

路径：已经做出的选择
选择列表：当前可以做的选择
结束条件：到达决策树的叶子节点，无法再做选择
做选择：将选择加入路径，更新选择列表
撤销选择：将选择从路径中移除，恢复选择列表，即回溯

1.3 回溯算法的应用场景

回溯算法常用于解决以下几类问题：

组合问题：N个数里按一定规则找出k个数的集合
排列问题：N个数按一定规则全排列，有几种排列方式
子集问题：一个N个数的集合里有多少符合条件的子集
棋盘问题：N皇后、数独等
切割问题：字符串切割等

1.4 回溯算法的效率分析

回溯算法的时间复杂度取决于以下几个因素：

问题的规模：问题的规模越大，回溯算法的时间复杂度越高
搜索空间的大小：搜索空间的大小取决于问题的约束条件和剪枝策略
剪枝的效率：有效的剪枝可以大大减少搜索空间，提高算法的效率

回溯算法的空间复杂度主要取决于递归调用栈的深度和存储结果所需的空间。

二、组合问题

2.1 组合总和（LeetCode 39）

题目描述：给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。

示例：输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]]

解题思路：这是一个典型的组合问题，我们可以使用回溯算法来解决。为了避免重复的组合（如[2,3,2]和[2,2,3]），我们需要对数组进行排序，并在回溯过程中限制下一次选择的起始索引。

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    // 对数组进行排序，便于剪枝
    Arrays.sort(candidates);
    backtrack(candidates, target, 0, 0, path, result);
    return result;
}

private void backtrack(int[] candidates, int target, int start, int sum, List<Integer> path, List<List<Integer>> result) {
    // 如果当前和等于目标值，将当前路径加入结果集
    if (sum == target) {
        result.add(new ArrayList<>(path));
        return;
    }
    // 如果当前和大于目标值，直接返回（剪枝）
    if (sum > target) {
        return;
    }
    // 从start开始选择，避免重复的组合
    for (int i = start; i < candidates.length; i++) {
        // 如果当前元素已经大于target - sum，后面的元素更大，直接返回（剪枝）
        if (candidates[i] > target - sum) {
            break;
        }
        // 做选择
        path.add(candidates[i]);
        // 递归，注意i不变，因为可以重复选择同一个元素
        backtrack(candidates, target, i, sum + candidates[i], path, result);
        // 撤销选择
        path.remove(path.size() - 1);
    }
}

2.2 组合总和 II（LeetCode 40）

题目描述：给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。

示例：输入：candidates = [10,1,2,7,6,1,5], target = 8 输出：[[1,1,6],[1,2,5],[1,7],[2,6]]

解题思路：这道题与组合总和的区别在于数组中可能有重复元素，且每个元素只能使用一次。我们需要在回溯过程中跳过重复的元素。

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    // 对数组进行排序，便于去重和剪枝
    Arrays.sort(candidates);
    backtrack(candidates, target, 0, 0, path, result, new boolean[candidates.length]);
    return result;
}

private void backtrack(int[] candidates, int target, int start, int sum, List<Integer> path, List<List<Integer>> result, boolean[] used) {
    // 如果当前和等于目标值，将当前路径加入结果集
    if (sum == target) {
        result.add(new ArrayList<>(path));
        return;
    }
    // 如果当前和大于目标值，直接返回（剪枝）
    if (sum > target) {
        return;
    }
    // 从start开始选择
    for (int i = start; i < candidates.length; i++) {
        // 如果当前元素已经大于target - sum，后面的元素更大，直接返回（剪枝）
        if (candidates[i] > target - sum) {
            break;
        }
        // 跳过重复的元素（同一层的重复元素）
        if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {
            continue;
        }
        // 做选择
        path.add(candidates[i]);
        used[i] = true;
        // 递归，注意i+1，因为每个元素只能使用一次
        backtrack(candidates, target, i + 1, sum + candidates[i], path, result, used);
        // 撤销选择
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

2.3 组合（LeetCode 77）

题目描述：给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例：输入：n = 4, k = 2 输出：[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]

解题思路：这是一个典型的组合问题，我们需要从1到n中选择k个数，且不考虑顺序。我们可以使用回溯算法来解决，通过限制下一次选择的起始数字来避免重复的组合。

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    backtrack(n, k, 1, path, result);
    return result;
}

private void backtrack(int n, int k, int start, List<Integer> path, List<List<Integer>> result) {
    // 如果当前路径的长度等于k，将当前路径加入结果集
    if (path.size() == k) {
        result.add(new ArrayList<>(path));
        return;
    }
    // 从start开始选择，避免重复的组合
    // 剪枝：i的上界可以优化为n - (k - path.size()) + 1
    for (int i = start; i <= n - (k - path.size()) + 1; i++) {
        // 做选择
        path.add(i);
        // 递归，注意i+1
        backtrack(n, k, i + 1, path, result);
        // 撤销选择
        path.remove(path.size() - 1);
    }
}

2.4 电话号码的字母组合（LeetCode 17）

题目描述：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。数字到字母的映射与电话按键相同。注意 1 不对应任何字母。

示例：输入：digits = “23” 输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

解题思路：这是一个组合问题，每个数字对应多个字母，我们需要为每个数字选择一个字母，然后组合起来。我们可以使用回溯算法来解决。

public List<String> letterCombinations(String digits) {
    List<String> result = new ArrayList<>();
    if (digits == null || digits.length() == 0) {
        return result;
    }
    // 数字到字母的映射
    Map<Character, String> phoneMap = new HashMap<>();
    phoneMap.put('2', "abc");
    phoneMap.put('3', "def");
    phoneMap.put('4', "ghi");
    phoneMap.put('5', "jkl");
    phoneMap.put('6', "mno");
    phoneMap.put('7', "pqrs");
    phoneMap.put('8', "tuv");
    phoneMap.put('9', "wxyz");
    StringBuilder path = new StringBuilder();
    backtrack(digits, 0, phoneMap, path, result);
    return result;
}

private void backtrack(String digits, int index, Map<Character, String> phoneMap, StringBuilder path, List<String> result) {
    // 如果已经处理完所有数字，将当前路径加入结果集
    if (index == digits.length()) {
        result.add(path.toString());
        return;
    }
    // 获取当前数字对应的字母
    char digit = digits.charAt(index);
    String letters = phoneMap.get(digit);
    // 为当前数字选择一个字母
    for (int i = 0; i < letters.length(); i++) {
        // 做选择
        path.append(letters.charAt(i));
        // 递归处理下一个数字
        backtrack(digits, index + 1, phoneMap, path, result);
        // 撤销选择
        path.deleteCharAt(path.length() - 1);
    }
}

三、排列问题

3.1 全排列（LeetCode 46）

题目描述：给定一个没有重复数字的序列，返回其所有可能的全排列。

示例：输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

解题思路：这是一个典型的排列问题，我们需要考虑元素的顺序。我们可以使用回溯算法来解决，通过一个used数组来标记哪些元素已经被使用过。

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    backtrack(nums, path, used, result);
    return result;
}

private void backtrack(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> result) {
    // 如果当前路径的长度等于数组的长度，将当前路径加入结果集
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));
        return;
    }
    // 尝试选择每个未使用的元素
    for (int i = 0; i < nums.length; i++) {
        // 如果元素已经被使用过，跳过
        if (used[i]) {
            continue;
        }
        // 做选择
        path.add(nums[i]);
        used[i] = true;
        // 递归
        backtrack(nums, path, used, result);
        // 撤销选择
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

3.2 全排列 II（LeetCode 47）

题目描述：给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例：输入：nums = [1,1,2] 输出：[[1,1,2],[1,2,1],[2,1,1]]

解题思路：这道题与全排列的区别在于数组中可能有重复元素，我们需要在回溯过程中跳过重复的元素。为了便于去重，我们首先需要对数组进行排序。

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    // 对数组进行排序，便于去重
    Arrays.sort(nums);
    backtrack(nums, path, used, result);
    return result;
}

private void backtrack(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> result) {
    // 如果当前路径的长度等于数组的长度，将当前路径加入结果集
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));
        return;
    }
    // 尝试选择每个未使用的元素
    for (int i = 0; i < nums.length; i++) {
        // 如果元素已经被使用过，跳过
        if (used[i]) {
            continue;
        }
        // 跳过重复的元素（同一层的重复元素）
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
            continue;
        }
        // 做选择
        path.add(nums[i]);
        used[i] = true;
        // 递归
        backtrack(nums, path, used, result);
        // 撤销选择
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

3.3 字符串的排列（LeetCode 567）

题目描述：给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例：输入：s1 = “ab” s2 = “eidbaooo” 输出：true 解释：s2 包含 s1 的排列之一 (ba).

解题思路：这道题可以看作是一个排列问题，但由于我们只需要判断是否存在一个排列是另一个字符串的子串，我们可以使用滑动窗口和哈希表来优化，而不是生成所有可能的排列。

public boolean checkInclusion(String s1, String s2) {
    int len1 = s1.length();
    int len2 = s2.length();
    if (len1 > len2) {
        return false;
    }
    // 统计s1中每个字符出现的次数
    int[] count1 = new int[26];
    for (char c : s1.toCharArray()) {
        count1[c - 'a']++;
    }
    // 使用滑动窗口遍历s2
    int[] count2 = new int[26];
    for (int i = 0; i < len2; i++) {
        // 将当前字符加入窗口
        count2[s2.charAt(i) - 'a']++;
        // 如果窗口的大小超过了s1的长度，移除窗口最左边的字符
        if (i >= len1) {
            count2[s2.charAt(i - len1) - 'a']--;
        }
        // 如果当前窗口的字符计数与s1的字符计数相同，返回true
        if (i >= len1 - 1 && Arrays.equals(count1, count2)) {
            return true;
        }
    }
    return false;
}

四、子集问题

4.1 子集（LeetCode 78）

题目描述：给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

示例：输入：nums = [1,2,3] 输出：[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

解题思路：这是一个典型的子集问题，我们可以使用回溯算法来解决。通过限制下一次选择的起始索引来避免重复的子集。

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    backtrack(nums, 0, path, result);
    return result;
}

private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
    // 将当前路径加入结果集（注意：这里不需要判断结束条件，因为每个路径都是一个子集）
    result.add(new ArrayList<>(path));
    // 从start开始选择，避免重复的子集
    for (int i = start; i < nums.length; i++) {
        // 做选择
        path.add(nums[i]);
        // 递归
        backtrack(nums, i + 1, path, result);
        // 撤销选择
        path.remove(path.size() - 1);
    }
}

4.2 子集 II（LeetCode 90）

题目描述：给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。

示例：输入：nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

解题思路：这道题与子集的区别在于数组中可能有重复元素，我们需要在回溯过程中跳过重复的元素。为了便于去重，我们首先需要对数组进行排序。

public List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    // 对数组进行排序，便于去重
    Arrays.sort(nums);
    backtrack(nums, 0, path, result);
    return result;
}

private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
    // 将当前路径加入结果集
    result.add(new ArrayList<>(path));
    // 从start开始选择，避免重复的子集
    for (int i = start; i < nums.length; i++) {
        // 跳过重复的元素（同一层的重复元素）
        if (i > start && nums[i] == nums[i - 1]) {
            continue;
        }
        // 做选择
        path.add(nums[i]);
        // 递归
        backtrack(nums, i + 1, path, result);
        // 撤销选择
        path.remove(path.size() - 1);
    }
}

4.3 递增子序列（LeetCode 491）

题目描述：给定一个整型数组，你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。

示例：输入：[4, 6, 7, 7] 输出：[[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

解题思路：这是一个子集问题的变种，我们需要找出所有递增的子序列。我们可以使用回溯算法来解决，并在回溯过程中确保子序列是递增的，同时跳过重复的元素。

public List<List<Integer>> findSubsequences(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    backtrack(nums, 0, path, result);
    return result;
}

private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
    // 如果当前路径的长度大于等于2，将当前路径加入结果集
    if (path.size() >= 2) {
        result.add(new ArrayList<>(path));
    }
    // 使用一个哈希表来记录当前层已经使用过的元素，避免重复
    Set<Integer> used = new HashSet<>();
    // 从start开始选择
    for (int i = start; i < nums.length; i++) {
        // 如果当前元素已经被使用过，跳过
        if (used.contains(nums[i])) {
            continue;
        }
        // 如果当前路径为空，或者当前元素大于等于路径最后一个元素，选择当前元素
        if (path.isEmpty() || nums[i] >= path.get(path.size() - 1)) {
            // 标记当前元素为已使用
            used.add(nums[i]);
            // 做选择
            path.add(nums[i]);
            // 递归
            backtrack(nums, i + 1, path, result);
            // 撤销选择
            path.remove(path.size() - 1);
        }
    }
}

五、棋盘问题

5.1 N皇后（LeetCode 51）

题目描述：n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。皇后可以攻击同一行、同一列或同一斜线上的棋子。

示例：输入：n = 4 输出：[ [“.Q…”, // 解法 1 “…Q”, “Q…”, “…Q.”],

[“…Q.”, // 解法 2 “Q…”, “…Q”, “.Q…”] ]

解题思路：这是一个经典的棋盘问题，我们可以使用回溯算法来解决。我们需要逐行放置皇后，并确保每行、每列、每条斜线上只有一个皇后。

public List<List<String>> solveNQueens(int n) {
    List<List<String>> result = new ArrayList<>();
    // 初始化棋盘
    char[][] board = new char[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(board[i], '.');
    }
    backtrack(board, 0, result);
    return result;
}

private void backtrack(char[][] board, int row, List<List<String>> result) {
    int n = board.length;
    // 如果已经放置了n个皇后，将当前棋盘加入结果集
    if (row == n) {
        List<String> solution = new ArrayList<>();
        for (char[] rowChars : board) {
            solution.add(new String(rowChars));
        }
        result.add(solution);
        return;
    }
    // 尝试在当前行的每一列放置皇后
    for (int col = 0; col < n; col++) {
        // 检查当前位置是否可以放置皇后
        if (isValid(board, row, col)) {
            // 做选择
            board[row][col] = 'Q';
            // 递归处理下一行
            backtrack(board, row + 1, result);
            // 撤销选择
            board[row][col] = '.';
        }
    }
}

private boolean isValid(char[][] board, int row, int col) {
    int n = board.length;
    // 检查列
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') {
            return false;
        }
    }
    // 检查左上到右下的斜线
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') {
            return false;
        }
    }
    // 检查右上到左下的斜线
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (board[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}

5.2 N皇后 II（LeetCode 52）

题目描述：n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。返回 n 皇后不同的解决方案的数量。

示例：输入：n = 4 输出：2

解题思路：这道题与N皇后的区别在于我们只需要返回解决方案的数量，而不需要返回具体的解决方案。我们可以使用回溯算法来解决，并在找到一个解决方案时增加计数器。

public int totalNQueens(int n) {
    int[] count = new int[1]; // 使用数组来存储结果，因为Java中的基本类型是值传递
    // 初始化棋盘
    char[][] board = new char[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(board[i], '.');
    }
    backtrack(board, 0, count);
    return count[0];
}

private void backtrack(char[][] board, int row, int[] count) {
    int n = board.length;
    // 如果已经放置了n个皇后，增加计数器
    if (row == n) {
        count[0]++;
        return;
    }
    // 尝试在当前行的每一列放置皇后
    for (int col = 0; col < n; col++) {
        // 检查当前位置是否可以放置皇后
        if (isValid(board, row, col)) {
            // 做选择
            board[row][col] = 'Q';
            // 递归处理下一行
            backtrack(board, row + 1, count);
            // 撤销选择
            board[row][col] = '.';
        }
    }
}

private boolean isValid(char[][] board, int row, int col) {
    int n = board.length;
    // 检查列
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') {
            return false;
        }
    }
    // 检查左上到右下的斜线
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') {
            return false;
        }
    }
    // 检查右上到左下的斜线
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (board[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}

5.3 解数独（LeetCode 37）

题目描述：编写一个程序，通过填充空格来解决数独问题。数独的解法需遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

示例：输入： [" [ [“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”] ]

解题思路：这是一个经典的数独问题，我们可以使用回溯算法来解决。我们需要逐行逐列地尝试填充空格，并确保每次填充都符合数独的规则。

public void solveSudoku(char[][] board) {
    backtrack(board);
}

private boolean backtrack(char[][] board) {
    int n = board.length;
    // 遍历棋盘的每一个位置
    for (int row = 0; row < n; row++) {
        for (int col = 0; col < n; col++) {
            // 如果当前位置已经有数字，跳过
            if (board[row][col] != '.') {
                continue;
            }
            // 尝试在当前位置填充1-9的数字
            for (char num = '1'; num <= '9'; num++) {
                // 检查当前数字是否可以放在当前位置
                if (isValid(board, row, col, num)) {
                    // 做选择
                    board[row][col] = num;
                    // 递归处理剩余的位置
                    if (backtrack(board)) {
                        return true;
                    }
                    // 撤销选择
                    board[row][col] = '.';
                }
            }
            // 如果当前位置无法填充任何数字，返回false
            return false;
        }
    }
    // 所有位置都已填充，返回true
    return true;
}

private boolean isValid(char[][] board, int row, int col, char num) {
    int n = board.length;
    // 检查行
    for (int i = 0; i < n; i++) {
        if (board[row][i] == num) {
            return false;
        }
    }
    // 检查列
    for (int i = 0; i < n; i++) {
        if (board[i][col] == num) {
            return false;
        }
    }
    // 检查3x3的宫
    int startRow = 3 * (row / 3);
    int startCol = 3 * (col / 3);
    for (int i = startRow; i < startRow + 3; i++) {
        for (int j = startCol; j < startCol + 3; j++) {
            if (board[i][j] == num) {
                return false;
            }
        }
    }
    return true;
}

六、切割问题

6.1 分割回文串（LeetCode 131）

题目描述：给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

示例：输入：s = “aab” 输出：[[“a”,“a”,“b”],[“aa”,“b”]]

解题思路：这是一个典型的切割问题，我们可以使用回溯算法来解决。我们需要逐位尝试切割字符串，并检查每个切割出的子串是否是回文串。

public List<List<String>> partition(String s) {
    List<List<String>> result = new ArrayList<>();
    List<String> path = new ArrayList<>();
    backtrack(s, 0, path, result);
    return result;
}

private void backtrack(String s, int start, List<String> path, List<List<String>> result) {
    // 如果已经切割到字符串的末尾，将当前路径加入结果集
    if (start == s.length()) {
        result.add(new ArrayList<>(path));
        return;
    }
    // 尝试从start位置开始切割
    for (int i = start; i < s.length(); i++) {
        // 检查子串s[start...i]是否是回文串
        if (isPalindrome(s, start, i)) {
            // 做选择
            path.add(s.substring(start, i + 1));
            // 递归处理剩余的字符串
            backtrack(s, i + 1, path, result);
            // 撤销选择
            path.remove(path.size() - 1);
        }
    }
}

private boolean isPalindrome(String s, int left, int right) {
    // 检查子串s[left...right]是否是回文串
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

6.2 复原IP地址（LeetCode 93）

题目描述：给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

示例：输入：s = “25525511135” 输出：[“255.255.11.135”,“255.255.111.35”]

解题思路：这是一个切割问题，我们需要将字符串切割成四个部分，每个部分都是有效的IP地址段。我们可以使用回溯算法来解决，通过深度优先搜索尝试所有可能的切割方式。

public List<String> restoreIpAddresses(String s) {
    List<String> result = new ArrayList<>();
    List<String> path = new ArrayList<>();
    backtrack(s, 0, 0, path, result);
    return result;
}

private void backtrack(String s, int start, int segmentCount, List<String> path, List<String> result) {
    int n = s.length();
    // 如果已经分割成4段，并且已经处理到字符串的末尾，将当前路径加入结果集
    if (segmentCount == 4 && start == n) {
        result.add(String.join(".", path));
        return;
    }
    // 如果已经分割成4段，但还没有处理到字符串的末尾，返回
    if (segmentCount == 4) {
        return;
    }
    // 尝试分割1-3位数字作为一个段
    for (int i = 1; i <= 3; i++) {
        // 如果剩余的字符不足以分割成当前段，跳过
        if (start + i > n) {
            break;
        }
        // 截取子串
        String segment = s.substring(start, start + i);
        // 检查子串是否是有效的IP地址段
        if (isValidSegment(segment)) {
            // 做选择
            path.add(segment);
            // 递归处理剩余的字符串
            backtrack(s, start + i, segmentCount + 1, path, result);
            // 撤销选择
            path.remove(path.size() - 1);
        }
    }
}

private boolean isValidSegment(String segment) {
    // 检查段是否有效
    int n = segment.length();
    // 如果段的长度大于1且以0开头，无效
    if (n > 1 && segment.charAt(0) == '0') {
        return false;
    }
    // 解析段的数值
    int num = Integer.parseInt(segment);
    // 检查段的数值是否在0-255之间
    return num >= 0 && num <= 255;
}

七、回溯算法的优化技巧

7.1 剪枝优化

剪枝是回溯算法中最重要的优化技巧之一，它可以帮助我们减少搜索空间，提高算法的效率。常见的剪枝策略包括：

可行性剪枝：在递归过程中，提前判断当前路径是否可行，如果不可行，直接返回，不再继续递归
最优性剪枝：在求解最优化问题时，如果当前路径已经不可能比已知的最优解更优，直接返回
重复状态剪枝：使用哈希表或集合来记录已经访问过的状态，避免重复搜索

7.2 状态压缩

对于某些问题，我们可以使用位运算来压缩状态，减少空间的使用。例如，在N皇后问题中，我们可以使用位掩码来表示哪些列、哪些对角线已经被皇后占据。

7.3 记忆化搜索

对于某些具有重叠子问题的回溯问题，我们可以使用记忆化搜索来优化，将已经计算过的子问题的结果缓存起来，避免重复计算。

7.4 迭代加深

对于某些搜索空间很大的问题，我们可以使用迭代加深的方法，逐步增加搜索的深度，这样可以保证找到的第一个解是最优的。

八、回溯算法的时间复杂度分析

回溯算法的时间复杂度通常比较高，它取决于以下几个因素：

问题的规模：问题的规模越大，回溯算法的时间复杂度越高
搜索空间的大小：搜索空间的大小取决于问题的约束条件和剪枝策略
剪枝的效率：有效的剪枝可以大大减少搜索空间，提高算法的效率

对于大多数回溯问题，时间复杂度通常是指数级或阶乘级的，例如：

组合问题：O(C(n, k))，其中n是元素的总数，k是要选择的元素的数量
排列问题：O(n!)，其中n是元素的总数
子集问题：O(2^n)，其中n是元素的总数
N皇后问题：O(n!)，其中n是皇后的数量

九、回溯算法与其他算法的对比

9.1 回溯算法与动态规划

回溯算法和动态规划都是解决组合优化问题的常用算法，它们的主要区别在于：

适用场景：回溯算法适用于需要枚举所有可能解的问题，而动态规划适用于具有重叠子问题和最优子结构的问题
效率：动态规划通过记忆化搜索或填表法来避免重复计算，通常比回溯算法更高效
结果：回溯算法可以找出所有可能的解，而动态规划通常只能找出最优解

9.2 回溯算法与贪心算法

回溯算法和贪心算法都是解决组合优化问题的常用算法，它们的主要区别在于：

策略：回溯算法通过尝试所有可能的选择来找出所有解，而贪心算法在每一步都做出局部最优的选择，希望通过这些局部最优的选择来得到全局最优解
结果：回溯算法可以找出所有可能的解，而贪心算法通常只能找出一个解（不一定是最优解）
效率：贪心算法通常比回溯算法更高效，但它并不适用于所有问题

9.3 回溯算法与分支限界法

回溯算法和分支限界法都是解决组合优化问题的常用算法，它们的主要区别在于：

搜索策略：回溯算法通常使用深度优先搜索，而分支限界法通常使用广度优先搜索或优先队列
剪枝策略：分支限界法通常使用更复杂的剪枝策略，如上下界剪枝
适用场景：分支限界法更适用于求解最优化问题，而回溯算法更适用于求解所有可能的解

十、总结与展望

回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。它的基本思想是：尝试所有可能的选择，如果当前选择无法得到解，则撤销该选择，回到上一步，尝试其他选择。

回溯算法常用于解决组合问题、排列问题、子集问题、棋盘问题和切割问题等。在实际应用中，我们需要根据问题的特点和需求来选择合适的回溯策略，并通过剪枝等优化技巧来提高算法的效率。

随着计算机科学的发展，回溯算法也在不断地演进和优化。例如，在人工智能领域，回溯算法被广泛应用于问题求解、博弈等；在大数据领域，回溯算法与并行计算、分布式计算等技术相结合，以应对大规模数据的挑战。

通过不断地学习和实践，我们可以更好地理解和应用回溯算法，为解决实际问题提供有力的支持。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-09-21，如有侵权请联系 cloudcommunity@tencent.com 删除

递归

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度