hot100 回溯专题

1 全排列存放结果res 存放临时的path 收集的时候要res.add(new LinkedList(path))要用一个boolean数组来表示本次循环nums[i]是否使用过每一次循环如果nums[i]使用过那就跳过此次循环表示当前轮选过了然后used[i]标记为truepath.add(nums[i]);递归调用backtracking回溯used[i]标记为false;path.remove(path.size() - 1);class Solution { ListListInteger res new ArrayList(); ListInteger path new LinkedList(); public ListListInteger permute(int[] nums) { boolean[] used new boolean[nums.length]; backtracking(nums, used); return res; } public void backtracking(int[] nums, boolean[] used) { int len nums.length; if (path.size() len) { res.add(new LinkedList(path)); return; } for (int i 0; i len; i) { if (used[i] true) { continue; } used[i] true; path.add(nums[i]); backtracking(nums, used); path.remove(path.size() - 1); used[i] false; } } }2 子集子集问题中「每一步路径都是有效子集」因此递归开头就收集路径递归终止条件是startIndex nums.length通过 startIndex 控制选择列表的起始位置避免回头选元素导致重复子集。class Solution { // 存储最终所有子集结果 ListListInteger res new ArrayList(); // 存储当前回溯的路径当前选中的元素 ListInteger path new ArrayList(); // 主方法入口返回所有子集 public ListListInteger subsets(int[] nums) { // 启动回溯从索引0开始选元素初始无元素选中 backtracking(nums, 0); return res; } // 回溯核心方法 // startIndex当前选择列表的起始索引控制只能往后选避免重复子集 public void backtracking(int[] nums, int startIndex) { // 核心每进入一次递归当前路径就是一个有效子集先加入结果集 // 注意必须新建LinkedList/ArrayList否则后续修改path会覆盖结果 res.add(new LinkedList(path)); // 终止条件起始索引超出数组长度 → 无元素可选返回 if (startIndex nums.length) { return; } // 遍历选择列表从startIndex开始避免回头选比如选了2就不再选1 for (int i startIndex; i nums.length; i) { // 1. 做出选择将当前元素加入路径 path.add(nums[i]); // 2. 递归下一轮从i1开始选保证只往后选 backtracking(nums, i 1); // 3. 撤销选择回溯移除最后一个元素尝试下一个选择 path.remove(path.size() - 1); } } }3 电话号码的字母组合先用str[]存数字对应的字符串可以先存两个空字符串。backtracking需要两个参数一个是输入字符串digits第二个是index表示到第几位数字了。回溯终止条件就是index digits.length()把sb.toString()加到res中。取出digits对应index的字符去str数组中取出字符串cur从0开始遍历cur。每加一个就index1递归调用。注意sb.deletCharAt(sb.length() - 1);要会写表示删除sb的最后一个字符。import java.util.ArrayList; import java.util.List; class Solution { // 全局变量存储最终的所有字母组合结果 ListString res new ArrayList(); // 全局变量临时拼接字母的容器避免频繁创建字符串提升效率 StringBuilder sb new StringBuilder(); // 数字到字母的映射表索引对应数字0-9值对应电话按键的字母 // 索引0、1为空因为0/1无对应字母索引2对应abc数字2以此类推 String[] str {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz}; /** * 入口方法返回电话号码对应的所有字母组合 * param digits 输入的数字字符串仅包含2-9 * return 所有字母组合的列表 */ public ListString letterCombinations(String digits) { // 调用回溯函数从第0个数字开始处理 backtracking(digits, 0); return res; } /** * 回溯核心函数递归遍历所有可能的字母组合 * param digits 输入的数字字符串 * param index 当前处理到digits的第几个数字索引 */ public void backtracking(String digits, int index) { // 终止条件处理完所有数字索引等于数字字符串长度 if (index digits.length()) { // 将当前拼接好的字母组合加入结果集 res.add(sb.toString()); return; // 回溯返回处理上一层的下一个字母 } // 1. 获取当前索引对应的数字字符转数字如2-2 int num digits.charAt(index) - 0; // 2. 根据数字获取对应的字母串如num2时curabc String cur str[num]; // 3. 遍历当前数字对应的所有字母 for (int i 0; i cur.length(); i) { // 选择将当前字母加入临时容器sb sb.append(cur.charAt(i)); // 递归处理下一个数字索引1 backtracking(digits, index 1); // 回溯撤销选择删除sb最后一个字母尝试当前数字的下一个字母 sb.deleteCharAt(sb.length() - 1); } } }4 组合总和可重复取sum target立即return, sum target就收集结果。回溯函数需要candidates[]数组需要target需要startIndex。组合问题里一个集合里取组合就需要startIndex递归的时候传入i还是i1表示是否能重复取。如果是多个集合取组合各个集合之间相互不影响那么就不用startIndex例如 电话号码的字母组合。而处理排列问题就不用使用startIndeximport java.util.ArrayList; import java.util.List; class Solution { // 全局变量存储当前正在拼接的组合路径 ListInteger path new ArrayList(); // 全局变量存储最终所有满足条件的组合结果 ListListInteger res new ArrayList(); // 全局变量存储当前路径中元素的累加和避免递归中频繁计算 int sum 0; /** * 入口方法返回所有和为target的组合 * param candidates 无重复元素的候选数组 * param target 目标和 * return 所有满足条件的组合列表 */ public ListListInteger combinationSum(int[] candidates, int target) { // 调用回溯函数从数组的第0个索引开始遍历 backtracking(candidates, target, 0); return res; } /** * 回溯核心函数递归遍历所有可能的组合 * param candidates 候选数组 * param target 目标和 * param startIndex 当前层遍历的起始索引控制不回头选避免重复组合 */ public void backtracking(int[] candidates, int target, int startIndex) { // 剪枝条件当前累加和超过目标值无需继续递归直接返回 if (sum target) { return; } // 终止条件当前累加和等于目标值找到有效组合 if (sum target) { // 注意必须新建ArrayList存入结果否则path后续回溯会修改结果 res.add(new ArrayList(path)); return; } // 遍历候选数组从startIndex开始避免重复组合如[2,3]和[3,2] for (int i startIndex; i candidates.length; i) { // 1. 选择将当前元素加入路径累加和增加 path.add(candidates[i]); sum candidates[i]; // 2. 递归处理下一层起始索引传i允许重复选当前元素 backtracking(candidates, target, i); // 3. 回溯撤销选择移除路径最后一个元素累加和减少 sum - candidates[i]; path.remove(path.size() - 1); } } }5 括号生成注意用StringBuilder来拼接字符删除最后一个用deleteCharAt(path.length() - 1)不是size()回溯函数传入左括号和右括号的数量left 、right两个约束条件left nright left;import java.util.ArrayList; import java.util.List; class Solution { // 存储最终的有效括号组合 private ListString result new ArrayList(); // 临时拼接括号的容器避免频繁创建字符串提升效率 private StringBuilder path new StringBuilder(); public ListString generateParenthesis(int n) { // 调用回溯函数初始左/右括号数量都为0 backtrack(n, 0, 0); return result; } /** * 回溯核心函数 * param n 括号的总对数 * param left 已使用的左括号数量 * param right 已使用的右括号数量 */ private void backtrack(int n, int left, int right) { // 终止条件生成的括号字符串长度等于2nn对括号 if (path.length() 2 * n) { result.add(path.toString()); // 加入结果集 return; } // 剪枝条件1左括号数量 n可添加左括号 if (left n) { // 选择添加左括号 path.append((); // 递归左括号数量1 backtrack(n, left 1, right); // 回溯删除最后一个字符撤销选择 path.deleteCharAt(path.length() - 1); } // 剪枝条件2右括号数量 左括号数量可添加右括号保证有效性 if (right left) { // 选择添加右括号 path.append()); // 递归右括号数量1 backtrack(n, left, right 1); // 回溯删除最后一个字符撤销选择 path.deleteCharAt(path.length() - 1); } } // 测试示例 public static void main(String[] args) { Solution solution new Solution(); int n 3; ListString res solution.generateParenthesis(n); System.out.println(res); // 输出[((())),(()()),(())(),()(()),()()()] } }6 单词搜索(难)dirs[][]用于控制四个方向backtracking要传入的参数board、visited、word、x、y、idx(遍历到word的第几个字符)found m n写在成员变量里面回溯函数开始found就提前return。否则idx到最后一个了表示找到了最后一个字符found truereturnbacktracking函数里面只有nextX、nextY不越界且visited[nextX][nextY]没有访问过且board[nextX][nextY] word.charAt(idx 1)才进入下一轮的递归主函数里两层for循环遍历找到第一个入口(word.charAt(0) borad[i][j])visted[i][j] true然后开始递归。二刷每次找到一个起点要么把visited[i][j]复原为false,要么新建一个visted[][]数组。用found标记找没找到如果找到了就在backtracking()函数里面提前return还有主函数里的for循环中提前return。class Solution { // 定义上下左右四个方向的偏移量行偏移、列偏移 private int[][] dirs {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 网格的行数、列数 private int m, n; // 标记是否找到目标单词提前终止回溯优化效率 private boolean found; public boolean exist(char[][] board, String word) { m board.length; n board[0].length; found false; // 1. 遍历网格的每一个位置作为回溯的起点 for (int i 0; i m; i) { for (int j 0; j n; j) { // 只有当前字符匹配单词第一个字符才启动回溯 if (board[i][j] word.charAt(0)) { // 访问标记数组记录当前路径已使用的单元格避免重复 boolean[][] visited new boolean[m][n]; visited[i][j] true; // 标记起点为已访问 // 调用回溯函数当前位置(i,j)匹配到单词的第0个字符 backtracking(board, word, visited, i, j, 0); // 提前终止找到单词后直接返回无需继续遍历 if (found) { return true; } } } } // 所有起点都遍历过未找到单词 return false; } /** * 回溯核心函数替代原DFS语义更贴合回溯 * param board 字符网格 * param word 目标单词 * param visited 访问标记数组true已访问false未访问 * param i 当前遍历的行坐标 * param j 当前遍历的列坐标 * param idx 当前已匹配到单词的第idx个字符 */ private void backtracking(char[][] board, String word, boolean[][] visited, int i, int j, int idx) { // 终止条件1已找到单词直接返回剪枝避免无效递归 if (found) { return; } // 终止条件2匹配到单词的最后一个字符 → 找到目标标记found为true if (idx word.length() - 1) { found true; return; } // 遍历四个方向尝试所有可能的路径回溯的“选择”阶段 for (int[] dir : dirs) { // 计算下一个位置的坐标 int nextI i dir[0]; int nextJ j dir[1]; // 检查下一个位置是否合法 // 1. 坐标未越界 2. 未被访问过 3. 字符匹配单词的下一个字符 if (nextI 0 nextI m nextJ 0 nextJ n !visited[nextI][nextJ] board[nextI][nextJ] word.charAt(idx 1)) { // 选择标记该位置为已访问加入当前路径 visited[nextI][nextJ] true; // 递归继续回溯匹配单词的下一个字符idx1 backtracking(board, word, visited, nextI, nextJ, idx 1); // 回溯撤销选择恢复该位置为未访问允许其他路径复用 visited[nextI][nextJ] false; } } } }7 分割回文串字符串从startIndex开始尝试分割出所有以startIndex为起点的回文子串每分割出一个回文子串就将其加入当前路径然后递归处理剩余的子串当startIndex遍历到字符串末尾时说明已完成一次有效分割将当前路径加入结果集辅助函数isPalind检查子串是否为回文正读和反读一致确保分割的子串符合要求。import java.util.ArrayList; import java.util.List; class Solution { // 全局变量存储当前分割出的回文子串组合路径 ListString path new ArrayList(); // 全局变量存储所有符合条件的分割结果 ListListString res new ArrayList(); /** * 入口方法返回字符串s的所有回文分割组合 * param s 待分割的字符串 * return 所有有效分割结果 */ public ListListString partition(String s) { // 调用回溯函数从字符串的第0个索引开始分割 backtracking(s, 0); return res; } /** * 回溯核心函数递归分割字符串收集回文子串组合 * param s 待分割的原字符串 * param startIndex 当前分割的起始索引控制分割范围避免重复分割 */ public void backtracking(String s, int startIndex) { // 终止条件分割起始索引超过/等于字符串长度 → 完成一次有效分割 if (startIndex s.length()) { // 注意新建ArrayList存入结果避免path后续回溯修改结果 res.add(new ArrayList(path)); return; } // 遍历从startIndex开始尝试分割出所有以startIndex为起点的子串 for (int i startIndex; i s.length(); i) { // 截取子串[startIndex, i]substring左闭右开所以i1 String subStr s.substring(startIndex, i 1); // 剪枝只有子串是回文才继续分割非回文直接跳过 if (isPalind(subStr)) { // 选择将回文子串加入当前路径 path.add(subStr); // 递归处理剩余子串起始索引变为i1分割点后移 backtracking(s, i 1); // 回溯撤销选择移除路径最后一个子串尝试下一个分割点 path.remove(path.size() - 1); } } } /** * 辅助函数判断字符串是否为回文 * param str 待判断的字符串 * return true是回文false不是回文 */ public boolean isPalind(String str) { int left 0; // 左指针从字符串头部开始 int right str.length() - 1;// 右指针从字符串尾部开始 // 双指针向中间靠拢逐一比较字符 while(left right) { // 字符不相等 → 不是回文 if(str.charAt(left) ! str.charAt(right)) { return false; } left; // 左指针右移 right--; // 右指针左移 } // 所有字符匹配 → 是回文 return true; } }8 N皇后验证合法性左上角斜线、右上角斜线、正上方看有没有‘Q’Array2List(char[][] chessboard)工具函数row写在backtracking函数的参数里面遍历col递归。每一层递归选row的一个位置。class Solution { ListListString res new ArrayList(); public ListListString solveNQueens(int n) { char[][] chessboard new char[n][n]; for(int i 0; i n; i) { Arrays.fill(chessboard[i], .); } backtracking(0, n, chessboard); return res; } public void backtracking(int row, int n, char[][] chessboard) { if(row n) { res.add(Array2List(chessboard)); return; } for(int col 0; col n; col) { if(isValid(row, col, n, chessboard)) { chessboard[row][col] Q; backtracking(row 1, n, chessboard); chessboard[row][col] .; } } } public boolean isValid(int row, int col, int n, char[][] chessboard) { for(int i 0; i row; i) { if(chessboard[i][col] Q) { return false; } } for(int i row - 1, j col - 1; i 0 j 0; i--, j--) { if(chessboard[i][j] Q) { return false; } } for(int i row - 1, j col 1; i 0 j n; i--, j) { if(chessboard[i][j] Q) { return false; } } return true; } public ListString Array2List(char[][] chessboard) { ListString res new ArrayList(); for(int i 0; i chessboard.length; i) { StringBuilder sb new StringBuilder(); for(int j 0; j chessboard[0].length; j) { sb.append(chessboard[i][j]); } res.add(sb.toString()); } return res; } }