最详细，最简单的力扣（leetcode）hot 100回溯篇讲解
引言
这里是阳明Coding，本次带来的是关于力扣 hot 100的回溯章节的内容。回溯章节的算法题难度还是挺高的，特别是N皇后问题之类的。然后在写的过程中我们也可以发现一些很明显的相同规律。比如是否需要每次递归是否需要携带索引。相关的终止条件怎么看
目录
全排列
题目分析
本题是全排列问题，给定一个不含重复数字的数组nums，要求返回其所有可能的全排列。
关键要求：每个排列必须包含所有数组元素元素顺序不同视为不同的排列每个元素在每个排列中只能使用一次
核心思路：回溯法 + 元素标记：使用used布尔数组标记已使用的元素确保每个元素在单个排列中只出现一次递归过程：当路径长度等于数组长度时，保存当前排列每次递归遍历所有元素，跳过已使用的元素选择可用元素加入路径，标记为已使用，递归处理下一层回溯时撤销选择（移除元素，取消标记）与子集问题的区别：全排列必须包含所有元素选择顺序影响结果（[1,2]和[2,1]视为不同排列）因此每次递归都从数组开头遍历，而非从某个索引开始
代码如下
class Solution { // 存储所有全排列结果的列表 List<List<Integer>> res = new ArrayList<>(); // 当前正在构建的排列（路径） List<Integer> path = new ArrayList<>(); // 标记数组中的元素是否已被使用 boolean[] used; public List<List<Integer>> permute(int[] nums) { // 初始化used数组，长度与输入数组相同 used = new boolean[nums.length]; // 开始回溯搜索 backtrack(nums); // 返回所有全排列结果 return res; } public void backtrack(int[] nums) { // 终止条件：当前路径长度等于数组长度，说明已经形成了一个完整排列 if (path.size() == nums.length) { // 将当前路径的拷贝添加到结果列表（必须新建列表，否则后续修改会影响已保存的结果） res.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); // 撤销选择：回溯，将当前数字从路径移除，并标记为未使用 used[i] = false; path.removeLast(); // 或 path.remove(path.size() - 1) } } }子集
题目分析
本题是子集问题，给定一个不含重复元素的整数数组nums，要求返回该数组所有可能的子集（幂集）。
关键要求：解集不能包含重复的子集子集顺序不限包括空集和数组本身
核心思路：回溯法构建组合树：每个元素都有两种状态：选或不选但使用循环递归可以更直观地枚举所有组合递归设计：使用index参数控制从数组的哪个位置开始选择每次递归先保存当前路径（一个子集）然后从index开始循环，依次选择元素加入路径递归处理后续元素（i+1），保证每个元素只考虑一次去重关键：通过index和循环起始位置i控制始终向后选择，避免产生顺序不同但元素相同的子集
代码如下
class Solution { // 存储所有子集的结果 List<List<Integer>> res = new ArrayList<>(); // 记录当前路径（当前子集） List<Integer> path = new ArrayList<>(); public List<List<Integer>> subsets(int[] nums) { if (nums.length == 0) return res; // 从第0个元素开始回溯 backtrack(nums, 0); return res; } public void backtrack(int[] nums, int index) { // 每次进入函数时，当前path就是一个新的子集 res.add(new ArrayList<>(path)); // 终止条件：索引越界 if (index >= nums.length) return; // 遍历从index开始的所有元素 for (int i = index; i < nums.length; i++) { // 选择当前元素 path.add(nums[i]); // 递归处理下一个元素（注意是i+1，避免重复使用） backtrack(nums, i + 1); // 撤销选择，回溯到上一步 path.removeLast(); } } }电话号码的字母组合
题目分析
本题是电话号码字母组合问题，给定一个数字字符串digits，每个数字对应手机键盘上的若干字母（2-9），要求返回所有可能的字母组合。这是一个典型的排列组合回溯问题。
核心思路：建立数字到字母的映射（2→"abc", 3→"def", …）。通过递归回溯遍历所有组合路径：每一层递归处理一个数字。遍历该数字对应的每个字母，将其加入临时组合。递归进入下一层处理下一个数字。回溯时删除最后添加的字母，尝试其他可能。当临时组合长度等于输入数字串长度时，将其加入结果集。
代码如下
class Solution { // 存储所有可能的字母组合结果 List<String> result = new ArrayList<>(); // 用于构建当前组合的临时字符串 StringBuilder sb = new StringBuilder(); public List<String> letterCombinations(String digits) { // 处理空输入的情况 if (digits == null || digits.length() == 0) return result; // 数字到字母的映射表，索引对应数字 String[] strs = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; // 从第一个数字开始回溯 backtrack(digits, strs, 0); return result; } public void backtrack(String digits, String[] strs, int num) { // 终止条件：已经处理完所有数字 if (num == digits.length()) { result.add(sb.toString()); return; } // 获取当前数字对应的字母字符串 String str = strs[digits.charAt(num) - '0']; // 遍历当前数字对应的所有字母 for (int i = 0; i < str.length(); i++) { // 选择当前字母 sb.append(str.charAt(i)); // 递归处理下一个数字 backtrack(digits, strs, num + 1); // 撤销选择，回溯到上一步 sb.deleteCharAt(sb.length() - 1); } } }组合总和
题目分析
本题是组合总和问题，给定一个无重复元素的候选数组candidates和一个目标数target，要求找出所有可以使数字和等于target的唯一组合。同一个数字可以无限制重复使用。
关键点：同一个数字可重复使用（与子集/组合问题不同）。组合结果中，不同顺序视为相同组合（需要去重）。需要优化剪枝避免无效搜索。
核心思路：排序数组，便于后续剪枝操作。使用回溯算法探索所有可能组合：每层递归从当前索引开始（i = idx），避免产生顺序不同的重复组合。累计当前组合的和sum。当sum == target时，保存当前组合。剪枝优化：排序后，如果当前数字加入已使sum > target，则后续更大数字也必然超过，直接break终止循环。
代码如下
class Solution { // 存储所有符合条件的组合 List<List<Integer>> res = new ArrayList<>(); // 记录当前组合 List<Integer> path = new ArrayList<>(); public List<List<Integer>> combinationSum(int[] candidates, int target) { // 排序有助于后续剪枝 Arrays.sort(candidates); // 从索引0开始回溯，初始和为0 backtrack(candidates, target, 0, 0); return res; } public void backtrack(int[] candidates, int target, int idx, int sum) { // 终止条件：当前和等于目标值 if (sum == target) { res.add(new ArrayList<>(path)); return; } // 从idx开始遍历，避免重复组合（允许重复使用同一元素） for (int i = idx; i < candidates.length; i++) { // 剪枝：如果加上当前元素已经超过目标值，则跳过 // 因为数组已排序，后续元素只会更大，所以可以直接break if (sum + candidates[i] > target) break; // 选择当前元素 path.add(candidates[i]); // 递归处理，注意idx传i（不是i+1），允许重复使用同一元素 backtrack(candidates, target, i, sum + candidates[i]); // 撤销选择，回溯 path.removeLast(); } } }括号生成
题目分析
本题是括号生成问题，给定数字n，要求生成所有有效的括号组合。有效括号组合必须满足：左括号和右括号数量相等（均为n对）任意前缀中，左括号数量不少于右括号数量
核心思路：使用回溯法构建括号字符串：维护当前已使用的左括号数open和右括号数close当前字符串长度达到2n时，保存有效组合剪枝条件：左括号数量未达上限（open < n）时可以添加左括号右括号数量小于左括号数量（close < open）时可以添加右括号关键特性：通过在递归过程中限制添加右括号的条件（必须close < open），自然保证了括号的有效性。
代码如下
class Solution { // 存储所有有效的括号组合 List<String> list = new ArrayList<>(); public List<String> generateParenthesis(int n) { // 初始为空字符串，开括号和闭括号数量都为0 backtrack("", n, 0, 0); return list; } public void backtrack(String current, int max, int open, int close) { // 终止条件：当前字符串长度达到最大长度（n对括号） if (current.length() == max * 2) { list.add(current); return; } // 如果开括号数量未达到最大值，可以添加开括号 // 开括号数量不能超过n if (open < max) { backtrack(current + "(", max, open + 1, close); } // 如果闭括号数量小于开括号数量，可以添加闭括号 // 这保证了括号的有效性（不会出现无效的闭括号） if (close < open) { backtrack(current + ")", max, open, close + 1); } } }单词搜索
题目分析
本题是单词搜索问题，给定一个二维字符网格board和一个字符串word，判断word是否存在于网格中。单词的构建规则为：字母在网格中必须是相邻单元格（上下左右四个方向）每个单元格在同一个单词中只能使用一次单词可以沿着任意方向构建
核心思路：深度优先搜索（DFS）+回溯：从网格的每个单元格开始尝试匹配单词的第一个字母对每个可能的起始点进行DFS搜索回溯的关键操作：使用used数组标记已访问的单元格，避免重复使用搜索后需要撤销标记（used[i][j]=false），允许其他路径使用该单元格剪枝条件：越界检查单元格已访问检查字符不匹配检查递归终止条件：成功：已匹配完单词所有字符（index==word.length()）失败：无法继续匹配（返回false）
代码如下
class Solution { // 记录单元格是否已被访问 boolean[][] used; public boolean exist(char[][] board, String word) { // 处理边界情况 if(board == null || board.length == 0 || board[0].length == 0 || word == null || word.length() == 0) return false; int m = board.length; int n = board[0].length; used = new boolean[m][n]; // 从每个单元格开始尝试搜索 for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(backtrack(board, word, 0, i, j)){ return true; } } } return false; } public boolean backtrack(char[][] board, String word, int index, int i, int j){ // 终止条件：已匹配完所有字符 if(index == word.length()){ return true; } // 边界检查、访问检查、字符匹配检查 if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || used[i][j] || board[i][j] != word.charAt(index)){ return false; } // 标记当前单元格为已访问 used[i][j] = true; // 向四个方向递归搜索 boolean found = backtrack(board, word, index + 1, i + 1, j) || // 向下 backtrack(board, word, index + 1, i, j + 1) || // 向右 backtrack(board, word, index + 1, i - 1, j) || // 向上 backtrack(board, word, index + 1, i, j - 1); // 向左 // 回溯：撤销访问标记 used[i][j] = false; return found; } }分割回文串
题目分析
本题是分割回文串问题，给定一个字符串s，要求将s分割成若干子串，使得每个子串都是回文串，返回所有可能的分割方案。
核心要求：字符串需要被完全分割，每个字符都必须属于某个回文子串所有子串都必须是回文的（正读反读相同）返回所有满足条件的分割方式
核心思路：回溯法 + 回文验证：从起始位置开始，尝试不同的分割点对于每个可能的子串，先验证是否为回文如果是回文，则加入当前路径，继续递归处理剩余部分关键步骤：使用start索引记录当前处理位置通过循环for(int i=start; ...)枚举所有可能的分割终点每次构建一个子串并检查是否为回文优化点：动态规划预处理回文判断可优化时间复杂度当前代码在每次递归时都检查回文，有一定重复计算
代码如下
class Solution { // 存储所有回文分割的结果 List<List<String>> result = new ArrayList<>(); // 记录当前的分割路径 List<String> path = new ArrayList<>(); public List<List<String>> partition(String s) { // 从索引0开始回溯，初始StringBuilder为空 backtrack(s, 0, new StringBuilder()); return result; } public void backtrack(String s, int start, StringBuilder sb) { // 终止条件：已处理完整个字符串 if (start == s.length()) { result.add(new ArrayList<>(path)); return; } // 遍历从start开始的所有可能的子串 for (int i = start; i < s.length(); i++) { // 将当前字符添加到StringBuilder中 sb.append(s.charAt(i)); // 检查当前子串是否为回文 if (check(sb)) { // 如果是回文，将其加入当前路径 path.add(sb.toString()); // 递归处理剩余部分，使用新的StringBuilder backtrack(s, i + 1, new StringBuilder()); // 回溯：撤销选择 path.removeLast(); } } } // 检查StringBuilder中的字符串是否为回文 public boolean check(StringBuilder sb) { for (int i = 0; i < sb.length() / 2; i++) { // 比较对称位置的字符 if (sb.charAt(i) != sb.charAt(sb.length() - 1 - i)) { return false; } } return true; } }N皇后
题目分析
本题是经典的N皇后问题，要求在n×n的棋盘上放置n个皇后，使得它们互不攻击（即任意两个皇后不能在同一行、同一列或同一斜线上）。需要返回所有不同的放置方案。
关键规则：每行必须且只能放置一个皇后每列最多只能有一个皇后每条对角线（主对角线和副对角线）上最多只能有一个皇后
核心思路：逐行回溯：由于每行必须放一个皇后，递归以行为单位进行在第row行尝试每一列位置（0到n-1）冲突检查：列检查：检查当前列是否已有皇后左上对角线：检查左上方向（行减列减）右上对角线：检查右上方向（行减列加）不需要检查行冲突（每行只放一个）不需要检查下方对角线（还未放置）保存结果：当成功放置到第n行（row==n）时，将当前棋盘状态转换为字符串列表保存
代码如下
class Solution { // 存储所有解决方案 List<List<String>> res = new ArrayList<>(); public List<List<String>> solveNQueens(int n) { // 初始化棋盘，全部填充为'.' char[][] board = new char[n][n]; for (char[] c : board) { Arrays.fill(c, '.'); } // 从第0行开始回溯 backtrack(board, n, 0); return res; } public void backtrack(char[][] board, int n, int row) { // 终止条件：所有行都已放置皇后 if (row == n) { res.add(buildArrayList(board)); return; } // 遍历当前行的每一列 for (int i = 0; i < n; i++) { // 检查当前位置是否可以放置皇后 if (check(board, row, i, n)) { // 放置皇后 board[row][i] = 'Q'; // 递归处理下一行 backtrack(board, n, row + 1); // 回溯：撤销放置 board[row][i] = '.'; } } } // 检查在(row, col)位置放置皇后是否有效 public boolean check(char[][] board, int row, int col, int n) { // 检查同一列上方是否有皇后 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; } // 将字符数组转换为字符串列表 public List<String> buildArrayList(char[][] ch) { List<String> list = new ArrayList<>(); for (char[] c : ch) { list.add(new String(c)); } return list; } }以上就是关于力扣 hot 100回溯章节的全部内容。有什么问题以及其他想法的可以在评论区进行留言，如果看到了都会进行一下回复。如果这篇博客文章对你有帮助，可以点赞收藏加关注。你们的支持是我更新的最大动力。
