跳到主要内容 回溯算法核心原理与 Java 实现详解 | 极客日志
Java java 算法
回溯算法核心原理与 Java 实现详解 本文介绍了回溯算法的基本概念、模板及在组合、切割、子集、排列、棋盘等问题中的应用。通过全排列、子集、电话号码字母组合、组合总和、括号生成、单词搜索、分割回文串及 N 皇后等经典例题，详细讲解了回溯法的递归逻辑、剪枝优化及 Java 代码实现。重点阐述了回溯树的构建、状态重置及终止条件，帮助读者掌握解决此类问题的通用方法。
LinuxPan 发布于 2026/3/27 回溯算法详解
1. 回溯方法概述
回溯法（Backtracking）也称为回溯搜索法，是一种通过递归探索所有可能解的搜索方式。回溯是递归的副产品，只要有递归就会有回溯。
1.1 适用问题类型
回溯法通常用于解决以下问题：
组合问题 ：从 N 个数中按规则找出 k 个数的集合。切割问题 ：字符串按规则有几种切割方式。子集问题 ：N 个数的集合里有多少符合条件的子集。排列问题 ：N 个数按规则全排列，有几种排列方式。棋盘问题 ：如 N 皇后、解数独等。
注意：组合无序，排列有序。
1.2 核心思想
回溯法解决的问题都可以抽象为树形结构。集合的大小构成树的宽度，递归的深度构成树的深度。递归必须有终止条件，因此必然是一棵高度有限的树（N 叉树）。
1.2.1 通用模板
void backtracking (参数) {
if (满足终止条件) {
存放结果;
return ;
}
for (选择 : 本层集合中元素) {
处理节点;
backtracking(路径，选择列表);
回溯，撤销处理结果;
}
}
2. 经典题目实战
2.1 全排列
题目描述 ：给定一个不含重复数字的数组 nums，返回其所有可能的全排列。
思路 ：
排列是有序的，元素在 [1,2] 和 [2,1] 中都要使用一次。处理排列问题不需要 startIndex，每层都是从 0 开始搜索。需要 used 数组记录 path 里已放置的元素。
import java.util.ArrayList;
import java.util.List;
public class Main {
List<List<Integer>> ans;
List<Integer> path;
public List<List<Integer>> permute (int [] nums) {
int n = nums.length;
ans = new ArrayList <>();
path = 微信扫一扫，关注极客日志 微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具 Keycode 信息 查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
Escape 与 Native 编解码 JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
JavaScript / HTML 格式化 使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
JavaScript 压缩与混淆 Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
加密/解密文本 使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
new
ArrayList
int
new
int
return
private
void
backtracking
(int [] nums, int [] used)
if
new
ArrayList
return
for
int
i
=
0
if
1
continue
1
0
1
public
static
void
main
(String[] args)
Main
main
=
new
Main
int
1
2
3
2.2 子集 题目描述 ：给你一个整数数组 nums，元素互不相同。返回该数组所有可能的子集（幂集）。
思路 ：
回溯，主要弄懂结束条件和子集合限制。每一个次递归要加入结果，没有 if 判断直接加。子集问题属于集合问题，每一次的子集合不从 0 开始，从 startIndex 开始。
import java.util.ArrayList;
import java.util.List;
public class Main {
List<List<Integer>> ans;
List<Integer> path;
public List<List<Integer>> subsets (int [] nums) {
ans = new ArrayList <>();
path = new ArrayList <>();
backtracking(nums, 0 );
return ans;
}
private void backtracking (int [] nums, int startIndex) {
ans.add(new ArrayList <>(path));
for (int i = startIndex; i < nums.length; i++) {
path.add(nums[i]);
backtracking(nums, i + 1 );
path.remove(path.size() - 1 );
}
}
public static void main (String[] args) {
Main main = new Main ();
int [] nums = {1 , 2 , 3 };
List<List<Integer>> ans = main.subsets(nums);
System.out.println(ans);
}
}
2.3 电话号码的字母组合 题目描述 ：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
思路 ：
回溯，使用哈希表模拟映射，使用 StringBuilder 来组装。
import java.util.*;
public class Main {
Map<Character, char []> map = new HashMap <>() {{
put('2' , new char []{'a' , 'b' , 'c' });
put('3' , new char []{'d' , 'e' , 'f' });
put('4' , new char []{'g' , 'h' , 'i' });
put('5' , new char []{'j' , 'k' , 'l' });
put('6' , new char []{'m' , 'n' , 'o' });
put('7' , new char []{'p' , 'q' , 'r' , 's' });
put('8' , new char []{'t' , 'u' , 'v' });
put('9' , new char []{'w' , 'x' , 'y' , 'z' });
}};
List<String> ans;
StringBuilder word;
public List<String> letterCombinations (String digits) {
ans = new ArrayList <>();
word = new StringBuilder ();
if (digits.isEmpty()) return ans;
backtracking(digits, 0 );
return ans;
}
private void backtracking (String digits, int index) {
if (word.length() == digits.length()) {
ans.add(word.toString());
return ;
}
char [] letters = map.get(digits.charAt(index));
for (char c : letters) {
word.append(c);
backtracking(digits, index + 1 );
word.deleteCharAt(word.length() - 1 );
}
}
public static void main (String[] args) {
Main main = new Main ();
List<String> ans = main.letterCombinations("23" );
System.out.println(ans);
}
}
2.4 组合总和 题目描述 ：给你一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合。
思路 ：
回溯，终止条件就是满足这个和。同一个数字可以无限重复使用，每一层的子集会逐渐缩减。
import java.util.ArrayList;
import java.util.List;
public class Main {
List<List<Integer>> ans;
List<Integer> path;
public List<List<Integer>> combinationSum (int [] candidates, int target) {
ans = new ArrayList <>();
path = new ArrayList <>();
backtracking(candidates, 0 , target);
return ans;
}
private void backtracking (int [] candidates, int startIndex, int target) {
if (target == 0 ) {
ans.add(new ArrayList <>(path));
return ;
} else if (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 );
}
}
public static void main (String[] args) {
Main main = new Main ();
int [] candidates = {2 , 3 , 6 , 7 };
List<List<Integer>> ans = main.combinationSum(candidates, 7 );
System.out.println(ans);
}
}
2.5 括号生成 题目描述 ：数字 n 代表生成括号的对数，设计函数生成所有可能的并且有效的括号组合。
当左括号数量 left < n 时还可以放左括号。
当右括号的数量 right < left 时可以放置右括号。
import java.util.ArrayList;
import java.util.List;
public class Main {
List<String> ans;
StringBuilder parentthesis;
public List<String> generateParenthesis (int n) {
ans = new ArrayList <>();
parentthesis = new StringBuilder ();
backtracking(0 , 0 , n);
return ans;
}
private void backtracking (int left, int right, int n) {
if (parentthesis.length() == 2 * n) {
ans.add(parentthesis.toString());
return ;
}
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 );
}
}
public static void main (String[] args) {
Main main = new Main ();
List<String> ans = main.generateParenthesis(3 );
System.out.println(ans);
}
}
2.6 单词搜索 题目描述 ：给定一个 m x n 二维字符网格 board 和一个字符串单词 word。如果 word 存在于网格中，返回 true。
思路 ：
DFS 回溯。满足条件就返回 true。需使用剪枝优化，避免超时。
public class Solution {
int [][] dir = {{-1 , 0 }, {0 , 1 }, {1 , 0 }, {0 , -1 }};
public boolean exist (char [][] board, String word) {
int m = board.length, n = board[0 ].length;
boolean [][] visited = new boolean [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 )) {
return true ;
}
}
}
return false ;
}
private boolean dfs (char [][] board, String word, boolean [][] visited, int x, int y, int index) {
if (index == word.length()) {
return true ;
}
if (x < 0 || x >= board.length || y < 0 || y >= board[0 ].length || visited[x][y] || !(word.charAt(index) == board[x][y])) {
return false ;
}
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 )) {
return true ;
}
}
visited[x][y] = false ;
return false ;
}
}
2.7 分割回文串 题目描述 ：将字符串 s 分割成一些子串，使每个子串都是回文串。
思路 ：
切割问题类似组合问题。递归用来纵向遍历，for 循环用来横向遍历。切割线切割到字符串的结尾位置，说明找到了一个切割方法。
import java.util.ArrayList;
import java.util.List;
public class Main {
List<List<String>> ans;
List<String> path;
public List<List<String>> partition (String s) {
ans = new ArrayList <>();
path = new ArrayList <>();
backtracking(s, 0 );
return ans;
}
private void backtracking (String s, int startIndex) {
if (startIndex >= s.length()) {
ans.add(new ArrayList <>(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 );
}
}
}
private boolean isHuiwen (String s, int left, int right) {
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false ;
}
left++;
right--;
}
return true ;
}
public static void main (String[] args) {
Main main = new Main ();
List<List<String>> ans = main.partition("aab" );
System.out.println(ans);
}
}
同类高频：复原 IP 地址 题目描述 ：给定一个只包含数字的字符串 s，返回所有可能的有效 IP 地址。
思路 ：
将字符串分 3 次分为 4 段。参数需要 startIndex 和分割次数计数 count。终止条件是 count == 3 且最后一个也是正确的。需要判断字符数字范围在 0~255，且无前导零。
import java.util.ArrayList;
import java.util.List;
public class Main {
List<String> ans;
public List<String> restoreIpAddresses (String s) {
ans = new ArrayList <>();
StringBuilder sb = new StringBuilder (s);
backtracking(sb, 0 , 0 );
return ans;
}
private void backtracking (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)) {
sb.insert(i + 1 , "." );
backtracking(sb, i + 2 , count + 1 );
sb.deleteCharAt(i + 1 );
} else {
break ;
}
}
}
private boolean isValid (String s, int left, int right) {
if (left > right) return false ;
if (s.charAt(left) == '0' && left != right) return false ;
if (right - left + 1 > 3 ) return false ;
try {
int num = Integer.parseInt(s.substring(left, right + 1 ));
return num >= 0 && num <= 255 ;
} catch (NumberFormatException e) {
return false ;
}
}
public static void main (String[] args) {
Main main = new Main ();
List<String> ans = main.restoreIpAddresses("25525511135" );
System.out.println(ans);
}
}
2.8 N 皇后 题目描述 ：将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
思路 ：
约束条件：不能同行、不能同列、不能同斜线。按行进行放置，一行只能放一个。Java 中 String 不可变，最好使用字符再拼接。
import java.util.ArrayList;
import java.util.List;
public class Main {
List<List<String>> ans;
public List<List<String>> solveNQueens (int n) {
char [][] board = new char [n][n];
for (int i = 0 ; i < n; i++) {
for (int j = 0 ; j < n; j++) {
board[i][j] = '.' ;
}
}
ans = new ArrayList <>();
backtracking(board, n, 0 );
return ans;
}
private void backtracking (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] = '.' ;
}
}
}
private boolean isValid (char [][] board, int n, int row, int col) {
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 ;
}
private List<String> charsToList (char [][] board, int n) {
List<String> res = new ArrayList <>();
for (char [] chars : board) {
res.add(String.copyValueOf(chars));
}
return res;
}
public static void main (String[] args) {
Main main = new Main ();
List<List<String>> ans = main.solveNQueens(4 );
System.out.println(ans);
}
}
