回溯
2026/1/14大约 11 分钟
回溯
回溯，通俗一点理解就是对一个数据进行一次变化，并对变化之后的数据进行操作记录，操作完成后将数据回溯到原本状态，再次进行下一次变化继续操作。
全排列
力扣题目链接：全排列
给定一个不含重复数字的数组 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]]
分析：如果让我们人手动去算，肯定是从前往后，第一个位置可能有n（数组长度）个数字可选，第二个位置就有n-1个，以此类推，最后数量是n的阶乘，我们可以用回溯模拟这种过程。
class Solution {
public List<List<Integer>> permute(int[] nums) {
//创建结果集合
List<List<Integer>> res = new ArrayList<List<Integer>>();
//表示当前排列的集合
List<Integer> cur = new ArrayList<Integer>();
// 赋初值
for(int num : nums){
cur.add(num);
}
//直接将长度传入
int length = nums.length;
deal(length, cur, res, 0);
return res;
}
private void deal(int length, List<Integer> cur, List<List<Integer>> res, int index){
//如果index到了length，说明所有的位置都已经结束了，此时的cur就是一个排列结果，将其放入
//要注意的是这里要new一个list，要不然放入多个cur引用，里面的集合是一样的
if(index == length){
res.add(new ArrayList<Integer>(cur));
}
//每个index位置都让后面的数来坐一坐，确定该index位置的数字之后，后面的继续递归调用方法确定后面的位置，每次确定之后都要回溯，保证该位置轮换时的正确性。
for(int i = index; i < length; i++){
Collections.swap(cur, index, i);
deal(length, cur, res, index + 1);
Collections.swap(cur, index, i);
}
}
}子集
力扣题目链接：子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]这个题目解法跟回溯关系不大，不做赘述，结题方法如下：
//每个元素能组成的集合是前面出现的集合与当前元素进行关联
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
res.add(new ArrayList<>());
int len = nums.length;
for(int i = 0; i < len; i++){
int size = res.size();
for(int j = 0; j < size; j++){
List<Integer> temp = new ArrayList<>(res.get(j));
temp.add(nums[i]);
res.add(temp);
}
}
return res;
}
}电话号码的字母组合
力扣题目链接：电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = "2"
输出：["a","b","c"]这个就很回溯了，跟那个全排列如出一辙，之前全排列每个index的元素都是数组中的元素，这个每个index的元素是数字所对应的字母数组中的元素。
class Solution {
//注意Map初始化的方法，Map.of()，里面的key，value等参数都用逗号分隔
Map<Character, String> map = Map.of('2', "abc", '3', "def", '4', "ghi", '5', "jkl", '6', "mno", '7', "pqrs", '8', "tuv", '9', "wxyz");
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
int len = digits.length();
traceBack(digits, res, len, 0, new StringBuffer());
return res;
}
public void traceBack(String digits, List<String> res, int len, int index, StringBuffer cur){
//同样，如果index跟输入长度相同说明排完了
if(index == len){
res.add(cur.toString());
}else{
char c = digits.charAt(index);
String letters = map.get(c);
for(int i = 0; i < letters.length(); i++){
cur.append(letters.charAt(i));
traceBack(digits, res, len, index + 1, cur);
//这里注意可变字符StringBuffer的删除索引元素的方法，叫做deleteCharAt()
cur.deleteCharAt(index);
}
}
}
}组合总和
力扣题目链接：组合总和
给你一个 无重复元素 的整数数组 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这也是一个回溯的问题，注意这里数组中的元素是可以重复的，所以每次选值都可以从数组遍历来选，这样就有一个问题，结果中会出现元素相同但顺序不同的数组，这是不合要求的，变成排列了。我们需要的是组合，因此实际递归过程中，我们还是要用index来记录位置，只取index之后的数，这样就能保证不会出现[2, 3]、[3, 2]的情况。
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
int len = candidates.length;
traceBack(candidates, target, 0, len, res, new ArrayList<Integer>());
return res;
}
public void traceBack(int[] candidates, int target, int index, int length, List<List<Integer>> res, List<Integer> cur){
int curLen = cur.size();
int sum = cur.stream().mapToInt(Integer::intValue).sum();
if(sum > target){
return;
}else if(sum == target){
res.add(new ArrayList<Integer>(cur));
return;
}else{
for(int i = index; i < length; i++){
cur.add(candidates[i]);
traceBack(candidates, target, i, length, res, cur);
cur.remove(cur.size() - 1);
}
}
}
}可以先给输入数组由小到大排序，然后剪枝操作，一旦大于target后面的就不用加了
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
// 1. 排序是为了方便后续剪枝
Arrays.sort(candidates);
traceBack(candidates, target, 0, res, new ArrayList<Integer>(), 0);
return res;
}
// 增加 begin 参数来控制搜索起点，增加 currentSum 避免重复计算 Stream
public void traceBack(int[] candidates, int target, int begin, List<List<Integer>> res, List<Integer> cur, int currentSum) {
if (currentSum == target) {
res.add(new ArrayList<>(cur));
return;
}
for (int i = begin; i < candidates.length; i++) {
// 2. 剪枝：如果当前和加上下一个数已经超了，直接跳出循环
if (currentSum + candidates[i] > target) {
break;
}
cur.add(candidates[i]);
// 3. 关键点：传入 i 而不是 i + 1，因为题目允许同一个数字无限制重复被选取
traceBack(candidates, target, i, res, cur, currentSum + candidates[i]);
cur.remove(cur.size() - 1);
}
}
}括号生成
力扣题目链接：括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
提示：
1 <= n <= 8要注意的是，肯定是先有左括号，才会有右括号，并且左括号的数量是小于n的，运算过程中右括号的数量是小于等于左括号的，因此回溯过程中需要递归左括号和右括号。
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
traceBack(res, n, 0, 0, new StringBuffer());
return res;
}
public void traceBack(List<String> res, int max, int open, int close, StringBuffer cur){
if(cur.length() == 2*max){
res.add(cur.toString());
return;
}
if(open < max){
cur.append('(');
traceBack(res, max, open + 1, close, cur);
cur.deleteCharAt(cur.length() - 1);
}
if(open > close){
cur.append(')');
traceBack(res, max, open, close + 1, cur);
cur.deleteCharAt(cur.length() - 1);
}
}
}单词搜索
力扣题目链接：单词搜索
给定一个 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
这个题目也比较简单，先找到一个首字母对应的位置，然后向其他位置进行回溯，这里要注意要把当前位置置为一个不用字符，防止广度优先搜索时重新找回去了。
class Solution {
// 将方向数组声明为 static final，避免每次创建对象都分配内存
private static final int[] DX = {0, 1, 0, -1};
private static final int[] DY = {1, 0, -1, 0};
public boolean exist(char[][] board, String word) {
int m = board.length;
int n = board[0].length;
// 提前转为 char[]，在递归中获取字符效率更高（避免多次调用 charAt）
char[] words = word.toCharArray();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 起点检查
if (board[i][j] == words[0]) {
if (dfs(board, words, 1, i, j)) {
return true;
}
}
}
}
return false;
}
private boolean dfs(char[][] board, char[] words, int index, int row, int col) {
// 出口：单词已全部匹配
if (index == words.length) {
return true;
}
// 直接从 board 中记录原始值，而不是根据 word 索引去推测
// 这样即使代码逻辑调整，还原现场也绝对不会出错
char temp = board[row][col];
board[row][col] = '#';
// 将 row 和 col 的加减放在递归参数里，避免在循环内反复修改原变量
// 这样代码更简洁，也减少了回退坐标的操作
for (int i = 0; i < 4; i++) {
int nx = row + DX[i];
int ny = col + DY[i];
// 边界检查 + 字符匹配检查
if (nx >= 0 && nx < board.length && ny >= 0 && ny < board[0].length
&& board[nx][ny] == words[index]) {
if (dfs(board, words, index + 1, nx, ny)) {
return true;
}
}
}
// 回溯：只需在所有方向尝试完毕后还原一次
board[row][col] = temp;
return false;
}
}分割回文串
力扣题目链接：分割回文串
给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
提示：
1 <= s.length <= 16
s 仅由小写英文字母组成class Solution {
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
List<String> cur = new ArrayList<>();
// 从字符串的第 0 个字符开始尝试分割
traceBack(cur, res, s, 0);
return res;
}
public void traceBack(List<String> cur, List<List<String>> res, String s, int index){
// 【递归出口】：如果 index 到达字符串末尾，说明找到了一种完整的分割方案
if(index == s.length()){
// 必须新建一个 ArrayList，否则 res 里面存的全是同一个 cur 的引用
res.add(new ArrayList<String>(cur));
return;
}
// i 代表当前这一步尝试切割的“终点”
for(int i = index; i < s.length(); i++){
// 截取从 index 到 i 的子串（左闭右开，所以是 i + 1）
String temp = s.substring(index, i + 1);
// 【剪枝/有效性判断】：只有当前截取的部分是回文，才继续往下走
if(valid(temp)){
cur.add(temp); // 将合法的回文子串放入当前路径
}
else{
// 如果当前部分不是回文，说明这种切法不行，跳过，尝试更长的切法
continue;
}
// 【递归】：基于当前的切割点，继续处理剩下未分割的字符串（从 i + 1 开始）
traceBack(cur, res, s, i + 1);
// 【回溯】：核心步骤！
// 当从递归返回时，说明刚才那条路走完了，需要把最后加进去的词删掉
// 这样才能在下一次循环中尝试把当前的 temp 变长（比如从 "a" 变成 "aa"）
cur.remove(cur.size() - 1);
}
}
// 双指针法判断字符串是否回文
private boolean valid(String s){
int start = 0;
int end = s.length() - 1;
while(start < end ){
// 如果头尾字符不相等，一定不是回文
if(s.charAt(start) != s.charAt(end)){
return false;
}
// 移动指针，向中间靠拢
start++;
end--;
}
return true;
}
}