回溯法的理论基础

这里参考代码随想录中的回溯章节。代码随想录 (programmercarl.com)

回溯法是一种搜索的方式，是穷举所有的可能选出我们想要的答案。但是由于回溯常常和递归结合在一起，所以回溯法会比较难以理解。

回溯法解决的问题

使用回溯算法求解的一般有组合，分割，子集，排列，棋盘等问题。

组合问题：N个数里按照一定规则找出k个数的集合

切割问题：一个字符串按照规则存在几种切割方式

子集问题：N个数的集合里有多少符合条件的子集

排列问题：N个数按一定规则全排列，存在几种排列方式

棋盘问题：N皇后，解数独等等

注意排列和组合的区别，组合不强调元素顺序，排列强调元素顺序。举个例子

{1,2},{2,1}为同一个组合，但是为两个不同的排列

理解回溯法

回溯法解决的问题可以抽象为树形结构。因为解决的都是在集合中递归查找子集，集合的大小为树的宽度，递归的深度构成树的深度

回溯法模板

• 回溯函数模板返回值以及参数

在回溯算法中，函数起名字为backtracking，这个起名随意。

回溯算法中函数返回值一般为void。

参数，因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。

void backtracking(参数)

• 回溯算法终止条件

既然是树形结构，遍历树形结构一定要有终止条件。

所以回溯也有要终止条件。

什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。

所以回溯函数终止条件伪代码如下：

if (终止条件) {存放结果;return;
}

• 回溯搜索的遍历过程

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

在这里插入图片描述

回溯函数遍历过程伪代码如下：

for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果
}

for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。

backtracking这里自己调用自己，实现递归。

大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。

• 模板如下

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}

46 全排列

46. 全排列

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

示例 1：

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

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

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

思路

先模拟一下全排列的搜索过程。从根节点搜索到叶子节点为递归，纵向遍历的过程。

1.回溯参数：在全排列问题中，我们需要一个标记数组来对当前数字是否使用过进行标记，因此需要传入的参数包括一个used数组。

2.终止条件：当递归搜索到叶子节点时，说明找到一个符合要求的全排列，可以终止并将当前排列假如结果集中。

3.单层搜索逻辑：如果当前数字未被使用过(used[i]=false),将used[i]置为true，之后继续搜索。如果使用过则跳过当前数字。

代码

最终代码如下。

注意终止条件这里

    //终止条件：递归搜索到叶子节点if(path.size()==nums.length){res.add(new ArrayList(path)); return; //注意这里要return，因为只有遍历到叶子节点时才会取结果}

需要res.add(new ArrayList(path)); 而不是直接res.add(path)

res.add(new ArrayList(path))是添加path的一个副本进入结果集。

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> permute(int[] nums) {/**用used数组来去重，不能用startIndex来控制不重复*/boolean[] used = new boolean[nums.length];backtracking(nums,used);return res;}private void backtracking(int[] nums,boolean[] used){//终止条件：递归搜索到叶子节点if(path.size()==nums.length){res.add(new ArrayList(path)); return; //注意这里要return，因为只有遍历到叶子节点时才会取结果}//3.单层搜索逻辑for(int i = 0;i<nums.length;i++){if(used[i]){  //用过的话，跳过当前数字。continue;}used[i]=true;path.add(nums[i]);backtracking(nums,used); //递归path.remove(path.size()-1);used[i] = false;}}}

78 子集

78. 子集

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

子集（幂集）。

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

示例 1：

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

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

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

思路

和全排列问题不同，全排列问题是收集树的叶子节点。而子集问题是找树的所有节点。本题中，无序并且取过的元素不会重复取，因此回溯遍历的时候，下一层需要从startIndex开始遍历（不能取之前取过的元素。）

​ 1.回溯传参：startIndex为开始搜索的下标，通过startIndex来记录本层递归中，集合从哪里遍历

​ 2.终止条件： startIndex>=nums.length的时候，return （注意要在终止条件前收集子集，因为每进入新一层的递归，都需要收集子集）

​ 3.单层处理逻辑

​ path.add(i)

    private void backtracking(int[] nums,int startIndex){//！！收集子集，每到达递归的新一层，就会生成新的子集。所以要在终止条件之前收集子集res.add(new ArrayList(path));if(startIndex>nums.length){return;}for(int i = startIndex;i<nums.length;i++){path.add(nums[i]); //子集收集元素backtracking(nums,i+1); //从i+1开始，元素不重复取path.remove(path.size()-1); //回溯}}

代码

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> subsets(int[] nums) {/**本题和之前的组合问题相似，由于数组中元素互不相同，所以不用判断相同的情况1.回溯传参：startIndex为开始搜索的下标，通过startIndex来记录本层递归中，集合从哪里遍历2.终止条件startIndex>=nums.length的时候，return3.单层处理逻辑path.add(i)*/backtracking(nums,0);return res;}private void backtracking(int[] nums,int startIndex){//！！收集子集，每到达递归的新一层，就会生成新的子集。所以要在终止条件之前收集子集res.add(new ArrayList(path));if(startIndex>nums.length){return;}for(int i = startIndex;i<nums.length;i++){path.add(nums[i]); //子集收集元素backtracking(nums,i+1); //从i+1开始，元素不重复取path.remove(path.size()-1); //回溯}}
}

17 电话号码的字母组合

17. 电话号码的字母组合

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

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

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

• 0 <= digits.length <= 4
• digits[i] 是范围 ['2', '9'] 的一个数字。

思路

算法思路

使用回溯算法生成所有可能的字母组合。回溯算法是一种通过试错来找到所有解决方案的算法。在这个问题中，我们需要生成所有可能的字母组合。

算法步骤

1. 初始化：定义一个字符串数组 num2String 来映射数字到对应的字母集合。
2. 递归终止条件：如果 path 的长度等于 digits 的长度，说明已经找到了一个完整的组合，将其添加到结果列表中。
3. 单层递归逻辑：使用 StringBuilder 来动态构建字符串，因为 String 是不可变的，每次修改都需要创建一个新的字符串对象。
4. 回溯：在递归调用后，使用 path.deleteCharAt() 删除最后一个字符，以便尝试下一个可能的字母。

代码

class Solution {List<String> res = new ArrayList<>();StringBuilder path = new StringBuilder();String[] num2String = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};public List<String> letterCombinations(String digits) {/**回溯回溯前需要定义数字->字符集的映射暴力搜索所有可能的组合1.递归终止条件：path.length() == digits.length()时，说明每个数字对应的字母都选择了一个2.单层递归逻辑注意，在这里由于需要不停的使用字符串拼接操作，所以用StringBuilder来实现path.append()path.deleteCharAt()3.注意String的用法String中获取某个位置的元素只能用charAt，数组才可以用下标获取。*/if(digits.length()==0||digits==null){return res;}backtracking(digits,0);return res;}private void backtracking(String digits,int index){ //index为当前digits中下标为index指向的数字if( index == digits.length()){ //遍历到digits结尾res.add(path.toString());return;}//index = 1,digits = "23" ,那么cur_num = digits[1] = 3int cur_num = digits.charAt(index)-'0';//遍历当前数组对应的字符集，比如当前数字为3,对应的字符集为“def”for(int i = 0;i<num2String[cur_num].length();i++){path.append(num2String[cur_num].charAt(i));backtracking(digits,index+1);path.deleteCharAt(path.length()-1);}}
}

39 组合总和

39. 组合总和

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

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

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

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

提示：

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• candidates 的所有元素 互不相同
• 1 <= target <= 40

思路

算法思路

无重复元素的整数数组candidates，但是其中的同一个数字可以被无限制重复选取。因此，本题仍然需要startIndex来横向控制往后的遍历。但是纵向就不需要向前，因为仍然可以使用当前指向的元素。backtracking(candidates,target,i); //注意！因为可重复选，所以这里递归传进的是i而非i+1

    for(int i = startIndex;i<candidates.length;i++){//2.单层搜索逻辑target -=candidates[i];path.add(candidates[i]);backtracking(candidates,target,i); //注意！因为可重复选，所以这里递归传进的是i而非i+1path.remove(path.size()-1);target += candidates[i];}

1.递归函数参数：使用两个全局变量。二维数组res存放结果集，数组path存放符合条件的结果。题目给出的参数，集合candidates和目标值target，每次用target减去当前的数字，当target==0说明找到结果。以及startIndex控制for循环的起始位置。

2.递归终止条件：当target<0时，再搜索下去没有意义，target=0时，需要收集结果。

3.单层搜索逻辑：从startIndex开始，搜索candidates集合。

代码

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {/**本题和77组合总和的区别在于本题中的元素可重复选取，并且没有对组合元素数量进行限制通过组合的和来限制树的深度for控制的是横向遍历，递归控制的是纵向遍历举个例子[2,5,3]在这里，可重复选说明递归的话，第一次在[2,5,3]中选，递归时仍然在[2,5,3]中选。那如何控制元素的往前遍历呢，通过for循环控制。*/backtracking(candidates,target,0);return res;}private void backtracking(int[] candidates,int target,int startIndex){//1.返回结果if(target<0){return;}if(target==0){res.add(new ArrayList(path));return;}for(int i = startIndex;i<candidates.length;i++){//2.单层搜索逻辑target -=candidates[i];path.add(candidates[i]);backtracking(candidates,target,i); //注意！因为可重复选，所以这里递归传进的是i而非i+1path.remove(path.size()-1);target += candidates[i];}}
}

22 括号生成

22. 括号生成

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

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

思路

• 回溯，通过记录左右括号的数量判断当前应该尝试放左括号还是右括号
• 回溯参数：左括号数量，右括号数量
• 终止条件：左括号数量为0且右括号数量为0，说明放完了
• 单层回溯逻辑：如果左括号数量大于0，放左括号，之后同样的逻辑放右括号

代码

class Solution {List<String> res = new ArrayList<>();StringBuilder path = new StringBuilder();public List<String> generateParenthesis(int n) {/**回溯，通过记录左右括号的数量判断当前应该尝试放左括号还是右括号回溯参数：左括号数量，右括号数量终止条件：左括号数量为0且右括号数量为0，说明放完了单层回溯逻辑：如果左括号数量大于0，放左括号，之后同样的逻辑放右括号*/backtracking(n,n);return res;}private void backtracking(int leftCount,int rightCount){if(leftCount == 0 && rightCount==0){res.add(path.toString());return;}//假如leftCount >rightCount,说明剩余的左括号数量大于右括号//只有剩余左括号数量<=右括号数量，才有可能组成合法的括号// (( ) 此时剩余左括号为1，右括号为2，有可能组成合法的括号// (())) 此时剩余左括号为1，右括号为0，不可能组成合法的括号if((leftCount != 0 || rightCount != 0) && leftCount <= rightCount){if(leftCount!=0){path.append('(');leftCount--;backtracking(leftCount,rightCount);leftCount++;path.deleteCharAt(path.length()-1);}if(rightCount!=0){path.append(')');rightCount--;backtracking(leftCount,rightCount);rightCount++;path.deleteCharAt(path.length()-1);}}}}

79 单词搜索

79. 单词搜索

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

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

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

示例 3：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

提示：

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board 和 word 仅由大小写英文字母组成

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

思路

​ 深搜
​ 以board中的每个位置为起点，向上下左右四个方向进行深度搜索
​ dfs参数：除了board，word，还包括当前匹配到的word中的index，以及搜索方向x，y
​ 返回条件：x，y溢出边界，board[x] [y]!=word[index]，board[x] [y]=‘.‘说明访问过
​ index = word.length()-1说明匹配成功
​ 单层搜索逻辑:匹配上了后给当前位置做个访问过的标记，即将当前位置元素置’.’,回溯完后再修改为原来的值

代码

class Solution {public boolean exist(char[][] board, String word) {/**回溯以board中的每个位置为起点，向上下左右四个方向进行深度搜索回溯参数：除了board，word，还包括当前匹配到的word中的index，以及搜索方向x，y返回条件：x，y溢出边界，board[x][y]!=word[index]，board[x][y]='.'说明访问过index = word.length()-1说明匹配成功单层搜索逻辑:匹配上了后给当前位置做个访问过的标记，即将当前位置元素置'.',回溯完后再修改为原来的值*/for(int i = 0;i<board.length;i++){for(int j = 0;j<board[0].length;j++){if(dfs(board,word,0,i,j)){return true;}}}return false;}private boolean dfs(char[][] board,String word,int index,int x,int y){//1.x,y溢出边界，当前元素不等于word中的字母，访问过if(x<0 || x>board.length-1 || y<0 || y>board[0].length-1 || word.charAt(index)!=board[x][y] || board[x][y]=='.' ){return false;}if(index == word.length()-1){return true;}char temp = board[x][y];board[x][y] = '.';boolean res = dfs(board,word,index+1,x-1,y) || dfs(board,word,index+1,x+1,y)||dfs(board,word,index+1,x,y-1) || dfs(board,word,index+1,x,y+1);board[x][y] = temp;return res;}
}

131 分割回文串

131. 分割回文串

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

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

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

思路

​ 分割问题也是用回溯来解决，具体如何回溯呢
​ 以aab为例，是要模拟切割线
​ aab 开始切割
​ 第一层 a|ab aa|b aab|
​ 第二层 a|a|b aa|b| 终止
​ 第三层 a|a|b| 终止
​ 可以看到startIndex此时为切割线在字符串中的位置
​ 1.回溯的参数：结果集，路径集，切割的位置
​ 2.回溯终止条件
​ 当切割线移动到String的末尾时，切割停止
​ 3.单层处理逻辑
​ 截取当且子串[startIndex,i]，如果当前子串是回文串，则将结果加入到路径中，递归（i+1）

回溯搜索图如下。

代码

class Solution {List<List<String>> res = new ArrayList<>();List<String> path = new ArrayList<>();public List<List<String>> partition(String s) {backtracking(s,0);return res;}private void backtracking(String s,int startIndex){//因为从起始位置一个个加的，所以结束时start一定=s.lengthif(startIndex==s.length()){//这里要创建path的copy版本res.add(new ArrayList(path));return;}for(int i = startIndex;i<s.length();i++){String substr = s.substring(startIndex,i+1);//截取子串[startIndex,i]if(check(substr)){path.add(substr);backtracking(s,i+1); //注意这里[startIndex,i]之间的已经被截取了，下一步要截取的为i+1开始的path.remove(path.size()-1);}}}//检查是否回文private boolean check(String s){for(int i = 0;i<s.length()/2;i++){if(s.charAt(i)!=s.charAt(s.length()-1-i)){return false;}}return true;}}

51 N皇后

51. N 皇后

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

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

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

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

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[["Q"]]

提示：

• 1 <= n <= 9

思路

本题中的回溯搜索为：for循环来搜索棋盘的每一列，递归来搜索棋盘的每一行。

• 回溯函数参数：row：当前搜索到第row行，board[] []为当前棋盘，n为棋盘总行数。

• 递归终止条件：当搜索到第n行时返回。

• 单层搜索逻辑：每一层的列都要从新一行的起始位置开始搜索，所以for循环从0开始。

• 判断合法位置

      //1.要在[row,col]位置填入Q//1.判断第row行其他位置是否存在Q// 在for循环中，每一行只会同时放一个Q，所以不用判断row行的其他位置是否存在Q//2.判断第col列其他位置是否存在Q,注意，由于此时row,n之间的行还没有遍历，所以不用考虑//3.判断斜对角线位置是否存在Q，注意，由于row+1还没有遍历到，所以只需要遍历row-1的情况//4.判断斜对角线位置是否存在Q
  

      //合法位置的判断private boolean isValid(char[][] board,int row,int col){int n = board[0].length;//1.要在[row,col]位置填入Q//1.判断第row行其他位置是否存在Q// 在for循环中，每一行只会同时放一个Q，所以不用判断row行的其他位置是否存在Q//2.判断第col列其他位置是否存在Q,注意，由于此时row,n之间的行还没有遍历，所以不用考虑for(int i = 0;i<row;i++){if(board[i][col]=='Q'){return false;}}//3.判断斜对角线位置是否存在Q，注意，由于row+1还没有遍历到，所以只需要遍历row-1的情况for(int i = row-1,j = col-1;i>=0&&j>=0;i--,j--){if(board[i][j]=='Q' && i!=row && j != col){return false;}}//4.判断斜对角线位置是否存在Qfor(int i = row-1,j = col+1;i>=0&&j<n;i--,j++){if(board[i][j]=='Q' && i!=row && j != col){return false;}}return true;}
  

回溯搜索过程如下。

代码

class Solution {List<List<String>> res = new ArrayList<>();public List<List<String>> solveNQueens(int n) {/**回溯参数：n一共有n行，row：当前搜索到第row行，board[][]为棋盘返回：当搜索到第n行时返回*/char[][] board = new char[n][n];for(char[] c: board){Arrays.fill(c,'.');}    backtracking(n,0,board);return res;}private void backtracking(int n,int row,char[][] board){if(row==n){List<String> tmp = Array2List(board);res.add(tmp);return;}for(int col = 0;col<n;col++){if(isValid(board,row,col)){board[row][col] = 'Q';backtracking(n,row+1,board);board[row][col] = '.';}}}//将得到的char[][]数组转换为List<String>private List<String> Array2List(char[][] board){List<String> temp = new ArrayList<>();for(char[] row:board){temp.add(new String(row));}return temp;}//合法位置的判断private boolean isValid(char[][] board,int row,int col){int n = board[0].length;//1.要在[row,col]位置填入Q//1.判断第row行其他位置是否存在Q// 在for循环中，每一行只会同时放一个Q，所以不用判断row行的其他位置是否存在Q//2.判断第col列其他位置是否存在Q,注意，由于此时row,n之间的行还没有遍历，所以不用考虑for(int i = 0;i<row;i++){if(board[i][col]=='Q'){return false;}}//3.判断斜对角线位置是否存在Q，注意，由于row+1还没有遍历到，所以只需要遍历row-1的情况for(int i = row-1,j = col-1;i>=0&&j>=0;i--,j--){if(board[i][j]=='Q' && i!=row && j != col){return false;}}//4.判断斜对角线位置是否存在Qfor(int i = row-1,j = col+1;i>=0&&j<n;i--,j++){if(board[i][j]=='Q' && i!=row && j != col){return false;}}return true;}
}