算法笔记-【回溯】

十 回溯

1 回溯方法

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。回溯是递归的副产品，只要有递归就会有回溯。

1.1 应对问题

回溯法，一般可以解决如下几种问题：

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

记住组合无序，排列有序，就可以了。

1.2 理解回溯

回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！

因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。

递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

1.3 模板

在上面我们提到了，回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。

如图：

注意图中，我特意举例集合大小和孩子的数量是相等的！

分析完过程，回溯算法模板框架如下： voidbacktracking(参数){if(终止条件){ 存放结果;return;}for(选择：本层集合中元素（树中节点孩子的数量就是集合的大小）){ 处理节点;backtracking(路径，选择列表);// 递归 回溯，撤销处理结果 }}

题目1——全排列【288】

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

示例 2：

示例 3：

提示：1 <= nums.length <= 6-10 <= nums[i] <= 10nums 中的所有整数 互不相同

思路：回溯

首先排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方。

可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用startIndex了。

• 每层都是从0开始搜索而不是startIndex
• 需要used数组记录path里都放了哪些元素了

但排列问题需要一个used数组，标记已经选择的元素，如图橘黄色部分所示:

/** * @author YinHang * @description 全排列 * @create 2026-02-28 20:14 */publicclassMain{publicList<List<Integer>> ans;publicList<Integer> path;publicList<List<Integer>>permute(int[] nums){int n = nums.length; ans =newArrayList<>(); path =newArrayList<>();// 回溯中传如参数used看那些数字已经使用，这个和组合不一样，组合传入一个startIndexint[] used =newint[n];backtracking(nums, used);return ans;}publicvoidbacktracking(int[] nums,int[] used){if(path.size()== nums.length){// ans.add(path);完全错误的写法，这个path是一个引用，存这个之后的变化也会在这里影响 ans.add(newArrayList<>(path));return;}for(int i =0; i < nums.length; i++){if(used[i]==1)continue;// 一定要写在这里 path.add(nums[i]); used[i]=1;backtracking(nums, used); used[i]=0; path.remove(path.size()-1);}}publicstaticvoidmain(String[] args){Main main =newMain();int[] nums =newint[]{1,2,3};List<List<Integer>> ans = main.permute(nums);for(List<Integer> an : ans){System.out.println(an.toString());}}}

题目2——子集【103】

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

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

示例 1：

示例 2：

提示：1 <= nums.length <= 10-10 <= nums[i] <= 10nums 中的所有元素 互不相同

思路：

回溯，主要弄懂结束条件和子集合限制，

每一个次递归要加入结果，没有if判断直接加，

子集问题也属于集合问题，每一次的子集合不从0开始，从startIndex开始

publicclassMain{List<List<Integer>> ans;List<Integer> path;publicList<List<Integer>>subsets(int[] nums){ ans =newArrayList<>(); path =newArrayList<>();backtracking(nums,0);return ans;}publicvoidbacktracking(int[] nums,int stratIndex){ ans.add(newArrayList<>(path));for(int i = stratIndex; i < nums.length; i++){ path.add(nums[i]);backtracking(nums, i +1); path.remove(path.size()-1);}}publicstaticvoidmain(String[] args){Main main =newMain();int[] nums =newint[]{1,2,3};List<List<Integer>> ans = main.subsets(nums);for(List<Integer> an : ans){System.out.println(an.toString());}}}

题目3——电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。



示例 1：

示例 2：

提示：1 <= digits.length <= 4digits[i] 是范围 ['2', '9'] 的一个数字。

思路：回溯，使用哈希表模拟映射，

使用StringBUilder来组装

/** * @author YinHang * @description 电话号码的字母组合 * @create 2026-02-28 21:10 */publicclassMain{Map<Character,char[]> map =newHashMap<Character,char[]>(){{put('2',newchar[]{'a','b','c'});put('3',newchar[]{'d','e','f'});put('4',newchar[]{'g','h','i'});put('5',newchar[]{'j','k','l'});put('6',newchar[]{'m','n','o'});put('7',newchar[]{'p','q','r','s'});put('8',newchar[]{'t','u','v'});put('9',newchar[]{'w','x','y','z'});}};List<String> ans;StringBuilder word;publicList<String>letterCombinations(String digits){ ans =newArrayList<>(); word =newStringBuilder();backtracking(digits,0);return ans;}publicvoidbacktracking(String digits,int index){if(word.length()== digits.length()){ ans.add(word.toString());return;}char[] letters = map.get(digits.charAt(index));for(int i =0; i < letters.length; i++){ word.append(letters[i]);backtracking(digits, index +1); word.deleteCharAt(index);}}publicstaticvoidmain(String[] args){Main main =newMain();List<String> ans = main.letterCombinations("23");System.out.println(ans.toString());}}

题目4——组合总和【91】

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

示例 2：

示例 3：

提示：1 <= candidates.length <= 302 <= candidates[i] <= 40candidates 的所有元素 互不相同1 <= target <= 40

思路：

回溯，终止条件就是满足这个和，维护一个和，属于组合问题。

但是很关键的就是同一个数字可以无限重复使用，每一层的子集会逐渐缩减。

/** * @author YinHang * @description 组合总和 * @create 2026-02-28 21:36 */publicclassMain{List<List<Integer>> ans;List<Integer> path;publicList<List<Integer>>combinationSum(int[] candidates,int target){ ans =newArrayList<>(); path =newArrayList<>();backtracking(candidates,0, target);return ans;}publicvoidbacktracking(int[] candidates,int startIndex,int target){if(target ==0){ ans.add(newArrayList<>(path));return;}elseif(target <0){return;}for(int i = startIndex; i < candidates.length; i++){ target -= candidates[i]; path.add(candidates[i]);backtracking(candidates, i,target); target += candidates[i]; path.remove(path.size()-1);}}publicstaticvoidmain(String[] args){Main main =newMain();int[] candidates =newint[]{2,3,6,7};List<List<Integer>> ans = main.combinationSum(candidates,7);for(List<Integer> an : ans){System.out.println(an.toString());}}}

题目5——括号生成【142】

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

示例 2：

提示：1 <= n <= 8

思路：第一次不太容易想出来

dfs回溯：关键点有两个，什么时候会可以放左左括号，什么时候可以放置右括号

1.当左括号数量left<n的时候还可以放左括号，因为整个字符串的长度一定要是2n，并且第一个一定是(

2.当右括号的数量right<左括号的数量left可以放置右括号，因为

/** * @author YinHang * @description 括号生成，回溯方法 * @create 2026-02-28 23:56 */publicclassMain{List<String> ans;StringBuilder parentthesis;publicList<String>generateParenthesis(int n){ ans =newArrayList<>(); parentthesis =newStringBuilder();backtracking(0,0, n);return ans;}publicvoidbacktracking(int left,int right,int n){if(parentthesis.length()==2* n){ ans.add(parentthesis.toString());return;}// 就两种情况(和),不用for，按照情况写出来if(left < n){ parentthesis.append("(");backtracking(left +1, right, n); parentthesis.deleteCharAt(parentthesis.length()-1);}if(right < left){ parentthesis.append(")");backtracking(left, right+1, n); parentthesis.deleteCharAt(parentthesis.length()-1);}}publicstaticvoidmain(String[] args){Main main =newMain();List<String> ans = main.generateParenthesis(3);System.out.println(ans.toString());}}

动态规划：

题目6——单词搜索【59】

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：



示例 2：



示例 3：



提示：m == board.lengthn = board[i].length1 <= m, n <= 61 <= word.length <= 15board 和 word 仅由大小写英文字母组成

**进阶：**你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

思路感觉就是dfs,满足条件就返回true,长度相当，内容相等

超时没有提前剪枝，我想的是使用StringBuilder进行拼装，但是实际上不用，超时版本

// 超时版本int[][] dir ={{-1,0},{0,1},{1,0},{0,-1}};StringBuilder sb;publicbooleanexist(char[][] board,String word){ sb =newStringBuilder();int m = board.length, n = board[0].length;boolean[][] visited =newboolean[m][n];for(int i =0; i < m; i++){for(int j =0; j < n; j++){if(board[i][j]== word.charAt(0)&&dfs(board, word, visited, i, j)){returntrue;}}}returnfalse;}publicbooleandfs(char[][] board,String word,boolean[][] visited,int x,int y){if(sb.toString().equals(word)){returntrue;}// 没有根据字母进行提前剪枝if(x <0|| x >= board.length || y <0|| y >= board[0].length || visited[x][y]){returnfalse;} sb.append(board[x][y]); visited[x][y]=true;boolean res =false;for(int i =0; i <4; i++){int nextx = x + dir[i][0];int nexty = y + dir[i][1];if(dfs(board, word, visited, nextx, nexty)){returntrue;}} sb.deleteCharAt(sb.length()-1); visited[x][y]=false;returnfalse;}

剪枝方法：

int[][] dir ={{-1,0},{0,1},{1,0},{0,-1}};publicbooleanexist(char[][] board,String word){int m = board.length, n = board[0].length;boolean[][] visited =newboolean[m][n];for(int i =0; i < m; i++){for(int j =0; j < n; j++){if(board[i][j]== word.charAt(0)&&dfs(board, word, visited, i, j,0)){returntrue;}}}returnfalse;}publicbooleandfs(char[][] board,String word,boolean[][] visited,int x,int y,int index){if(index == word.length()){returntrue;}if(x <0|| x >= board.length || y <0|| y >= board[0].length || visited[x][y]||!(word.charAt(index)==board[x][y])){returnfalse;} visited[x][y]=true;for(int i =0; i <4; i++){int nextx = x + dir[i][0];int nexty = y + dir[i][1];if(dfs(board, word, visited, nextx, nexty,index +1)){returntrue;}} visited[x][y]=false;returnfalse;}

题目7——分割回文串

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

示例 1：

示例 2：

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

思路：

我们来分析一下切割，其实切割问题类似组合问题。

例如对于字符串abcdef：

• 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个…。
• 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段…。

所以切割问题，也可以抽象为一棵树形结构，如图：

递归用来纵向遍历，for循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。

此时可以发现，切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。

所以就是找结尾位置

参数：需要一个startIndex

终止条件：startIndex>s.length()，这个分割就是成功

单层逻辑：需要s[startIndex: i]是回文，是就加入path

List<List<String>> ans;List<String> path;publicList<List<String>>partition(String s){ ans =newArrayList<>(); path =newArrayList<>();backtracking(s,0);return ans;}publicvoidbacktracking(String s,int startIndex){if(startIndex >= s.length()){ ans.add(newArrayList<>(path));return;}for(int i = startIndex; i < s.length(); i++){String subStr = s.substring(startIndex, i+1);if(ishuiwen(subStr)){ path.add(subStr);}else{continue;}backtracking(s, i +1);//  path.remove(path.size()-1);}}publicbooleanishuiwen(String s){if(s.isEmpty()){returnfalse;}elseif(s.length()==1){returntrue;}int left =0, right = s.length()-1;while(left <= right){if(s.charAt(left)!= s.charAt(right)){returnfalse;} left++; right--;}returntrue;}

在优化一下：String subStr = s.substring(startIndex, i+1);这一句放在回文判断通过后，使用原字符串进行回文判断。

List<List<String>> ans;List<String> path;publicList<List<String>>partition(String s){ ans =newArrayList<>(); path =newArrayList<>();backtracking(s,0);return ans;}publicvoidbacktracking(String s,int startIndex){if(startIndex >= s.length()){ ans.add(newArrayList<>(path));return;}for(int i = startIndex; i < s.length(); i++){// 直接基于原来的判断if(ishuiwen(s, startIndex, i)){String subStr = s.substring(startIndex, i+1); path.add(subStr);backtracking(s, i +1); path.remove(path.size()-1);}}}// 【修改点】：接收原字符串和左右边界publicbooleanishuiwen(String s,int left,int right){// 前面的 isEmpty 和 length==1 的判断可以删了，while 循环自然能处理while(left < right){// 【修复手滑 Bug】：用 left 和 right 比较if(s.charAt(left)!= s.charAt(right)){returnfalse;} left++; right--;}returntrue;}

[同类高频]复原IP地址【175】

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "[email protected]" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

示例 2：

示例 3：

提示：1 <= s.length <= 20s 仅由数字组成

现在判断是否是有效的ip地址，将字符串分3次分为4段，树就是3层，同样是分割问题：

参数：需要一个startIndex，分割次数计数count，也就上添加都点

终止条件：count==3，并且最后一个也是正确的，这个分割就是成功，加入结果

单层逻辑：需要s[startIndex: i]是不是正确的ip段，是就加入path

最主要的需要有1个判断字符数字范围在0~255

最难的地方在于ip段合法性的判断：

主要关键点在于：前导零是肯定不会有的，然后就是，长度超过3的数字直接也是false

publicbooleanisValid(String s,int left,int right){// 做判断if(left>right){returnfalse;}// 前导零不可以存在，但是单独0可以存在if(s.charAt(left)=='0'&& left != right){returnfalse;}// 长度不可以超过3if(right - left +1>3){returnfalse;}int num =Integer.parseInt(s.substring(left, right +1));return num >=0&& num <=255;}

完整代码：

List<String> ans;publicList<String>restoreIpAddresses(String s){ ans =newArrayList<>();StringBuilder sb =newStringBuilder(s);backtracking(sb,0,0);return ans;}publicvoidbacktracking(StringBuilder sb,int startIndex,int count){if(count ==3){if(isValid(sb.toString(), startIndex, sb.length()-1)){ ans.add(sb.toString());}return;}for(int i = startIndex; i < sb.length(); i++){if(isValid(sb.toString(), startIndex, i)){// 判断startIndex-i的数字符合条件，那么在这个数字后面加.，也就上i+1位置 sb.insert(i+1,".");// 回溯下一层就从i+2开始是数字backtracking(sb, i+2, count +1); sb.deleteCharAt(i+1);}else{// 直接结束本层循环break;}}}publicbooleanisValid(String s,int left,int right){// 做判断if(left>right){returnfalse;}// 前导零不可以存在，但是单独0可以存在if(s.charAt(left)=='0'&& left != right){returnfalse;}// 长度不可以超过3if(right - left +1>3){returnfalse;}int num =Integer.parseInt(s.substring(left, right +1));return num >=0&& num <=255;}

题目8——N皇后【】

不多但是很难

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

示例 2：

提示：1 <= n <= 9

首先来看一下皇后们的约束条件：

1. 不能同行
2. 不能同列
3. 不能同斜线

确定完约束条件，来看看究竟要怎么去搜索皇后们的位置，其实搜索皇后的位置，可以抽象为一棵树。

下面我用一个 3 * 3 的棋盘，将搜索过程抽象为一棵树，如图：

从图中，可以看出，二维矩阵中矩阵的高就是这棵树的高度，矩阵的宽就是树形结构中每一个节点的宽度。

那么我们用皇后们的约束条件，来回溯搜索这棵树，只要搜索到了树的叶子节点，说明就找到了皇后们的合理位置了。

按行进行放置，最后的结果放置也是按照行进行放置的，一行只能放一个，放完就直接放进path

还要注意java中String是不可变的，所以最好使用字符再拼接

List<List<String>> ans;publicList<List<String>>solveNQueen(int n){char[][] board =newchar[n][n];for(int i =0; i < n; i++){for(int j =0; j < n; j++){ board[i][j]='.';}} ans =newArrayList<>();backtracking(board, n,0);return ans;}publicvoidbacktracking(char[][] board,int n,int row){if(row >= n){ ans.add(charsToList(board, n));return;}for(int i =0; i < n; i++){if(isValid(board, n, row, i)){ board[row][i]='Q';backtracking(board, n, row+1); board[row][i]='.';}}}// 这个位置的放置是否合理,最关键publicbooleanisValid(char[][] board,int n,int row,int y){// 1.同行没有，每行放一个已经解决// 2.同列没有,y这一列for(int i =0; i < row; i++){if(board[i][y]=='Q'){returnfalse;}}// 3.45度主对角线没有for(int i =1; i <= row; i++){int col = y - i;if(col >=0&& board[row - i][col]=='Q'){returnfalse;}}// 4.135度副对角线没有for(int i =1; i <= row; i++){int col = y + i;if(col < n && board[row - i][col]=='Q'){returnfalse;}}returntrue;}publicList<String>charsToList(char[][] board,int n){List<String> res =newArrayList<>();for(char[] chars : board){ res.add(String.copyValueOf(chars));}return res;}

更加清爽的写法：

List<List<String>> ans;publicList<List<String>>solveNQueens(int n){char[][] board =newchar[n][n];for(int i =0; i < n; i++){for(int j =0; j < n; j++){ board[i][j]='.';}} ans =newArrayList<>();backtracking(board, n,0);return ans;}publicvoidbacktracking(char[][] board,int n,int row){if(row >= n){ ans.add(charsToList(board, n));return;}for(int i =0; i < n; i++){if(isValid(board, n, row, i)){ board[row][i]='Q';backtracking(board, n, row+1); board[row][i]='.';}}}// 这个位置的放置是否合理,最关键publicbooleanisValid(char[][] board,int n,int row,int col){// 1.同行没有，每行放一个已经解决// 2.同列没有,y这一列for(int i =0; i < row; i++){if(board[i][col]=='Q'){returnfalse;}}// 3.45度主对角线没有for(int i = row-1, j=col-1; i >=0&&j>=0; i--, j--){if(board[i][j]=='Q'){returnfalse;}}// 4.135度副对角线没有for(int i = row-1, j=col+1; i >=0&&j<n ; i--, j++){if(board[i][j]=='Q'){returnfalse;}}returntrue;}publicList<String>charsToList(char[][] board,int n){List<String> res =newArrayList<>();for(char[] chars : board){ res.add(String.copyValueOf(chars));}return res;}