回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
回溯是递归的副产品，只要有递归就会有回溯。
所以以下讲解中，回溯函数也就是递归函数，指的都是一个函数。
- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等
可以抽象为图形结构，树形结构
回溯函数伪代码如下：
void backtracking(参数)- 回溯函数终止条件（在叶子节点收集结果）
所以回溯函数终止条件伪代码如下：
if (终止条件) { 存放结果; return; }
回溯函数遍历过程伪代码如下：
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
77. 组合
本题关于剪枝操作是大家要理解的重点，因为后面很多回溯算法解决的题目，都是这个剪枝套路。
题目链接/文章讲解：代码随想录
视频讲解：带你学透回溯算法-组合问题（对应力扣题目：77.组合）| 回溯法精讲！_哔哩哔哩_bilibili
复习语法知识：
LinkedList 是 Java 集合框架中的一个类，继承自 AbstractSequentialList，实现了 List、Deque 接口。与 ArrayList 不同，LinkedList 基于链表结构（节点连接）。它不仅可以用作普通的列表（List），还可以充当 栈、队列、双端队列（Deque）。
✅ LinkedList 作为栈：
栈的特点是 后进先出（LIFO），而 LinkedList 提供了非常适合这种操作的方法，特别是：
addFirst()/removeFirst()：从链表头部添加或删除元素addLast()/removeLast()：从链表尾部添加或删除元素peekFirst()/peekLast()：查看链表头或尾部的元素
class Solution {
LinkedList<Integer>path=new LinkedList<>();
List<List<Integer>> res=new ArrayList<>();//返回的集合
public List<List<Integer>> combine(int n, int k) {
//List是一个接口， Integer为泛型
back(n,k,1);
return res;}
//以下为回溯函数
public void back(int n,int k,int startindex)
{
if(path.size()==k)//抵达最终的叶子节点,回溯结束
{
res.add(new ArrayList<>(path));
return;
}
for(int i=startindex;i<=n;i++)//starindex控制不能重复，因为是组合
{
path.add(i);
back(n,k,i+1);//调用回溯函数
path.removeLast();//要将末尾元素弹出，再进入新的元素，使用双向链表，便于弹出首尾元素
}
}
}res.add(new ArrayList<>(path));
new ArrayList<>(path)：
这是创建一个新的 ArrayList，并将 path 的内容复制到新的 ArrayList 中。
path是一个LinkedList<Integer>，用来记录当前的组合路径。new ArrayList<>(path)：通过传入path，将path中的所有元素复制到一个新的ArrayList中。这个操作非常关键，目的是创建一个全新的列表对象，否则path的引用会继续变化，导致res中的多个元素都指向同一个path对象，导致结果错误。为什么需要复制而不是直接添加
path呢？path是在回溯过程中动态改变的。如果直接add(path)，每次修改path的时候，res中的所有元素都会受到影响。为了防止这种情况，我们需要创建一个新的ArrayList，让它存储path的快照，从而避免引用问题。
剪枝操作：
class Solution {
LinkedList<Integer>path=new LinkedList<>();
List<List<Integer>> res=new ArrayList<>();//返回的集合
public List<List<Integer>> combine(int n, int k) {
//List是一个接口， Integer为泛型
back(n,k,1);
return res;}
//以下为回溯函数
public void back(int n,int k,int startindex)
{
if(path.size()==k)//抵达最终的叶子节点,回溯结束
{
res.add(new ArrayList<>(path));
return;
}
for(int i=startindex;i<=n-(k-path.size())+1;i++)//starindex控制不能重复，因为是组合
{
path.add(i);
back(n,k,i+1);//调用回溯函数
path.removeLast();//要将末尾元素弹出，再进入新的元素，使用双向链表，便于弹出首尾元素
}//控制递归深度的是path.size()
}
}剪枝操作的区别：如果剩余可选的元素小于还需要选择的元素，不进行遍历回溯
剩余可选的元素(i-n)：n-i+1
还需要选择的元素:k-path.size()
可得i<=n-(k-path.size())+1
for进行横向遍历，back()进行纵向深度遍历，每个back()中包含一个for循环
回溯三部曲（我往路上放了一块石头（add），然后继续往前走（递归）。
如果走到尽头（满足条件），我记录下这条路，然后回退，把石头拿起来（removeLast()），去试别的方向。”）
for (int i = startindex; i <= ...; i++) {
path.add(i); // 第一步：做选择
back(n, k, i + 1); // 第二步：递归进入下一层
path.removeLast(); // 第三步：撤销选择（回溯）
}
推导剪枝条件：
步骤 1️⃣：当前还需要选多少个数？
rest = k - path.size()
步骤 2️⃣：从 i 开始到 n 一共有多少个数可选？
available = n - i + 1
条件是：可选数量 >= 需要数量
n - i + 1 >= k - path.size()
两边同时移项：
i <= n - (k - path.size()) + 1 ✅
时间复杂度：
空间复杂度：
216.组合总和III
如果把 组合问题理解了，本题就容易一些了。
题目链接/文章讲解：代码随想录
视频讲解：和组合问题有啥区别？回溯算法如何剪枝？| LeetCode：216.组合总和III_哔哩哔哩_bilibili
class Solution {
LinkedList<Integer>path=new LinkedList<>();
List<List<Integer>>res=new ArrayList<>();//注意接口和实现类
public List<List<Integer>> combinationSum3(int k, int n) {
back(n,k,1,0);
return res;}
public void back(int n,int k,int startindex,int sum)
{
if(path.size()==k&&sum==n)
{
res.add(new LinkedList<>(path));
return;}//递归截止条件
for(int i=startindex;i<=9;i++)
{
path.add(i);
back(n,k,i+1,sum+i);
path.removeLast();//先把所有组合数都找出来
}
}}
修改回溯函数的参数：追踪他的总和
sum是在函数调用时每次计算sum + i传进去的每一层递归都有独立的 sum 副本，互不干扰
所以不需要显式回溯 sum
| 项目 | 建议 |
|---|---|
如果你使用 sum + i 传参 |
可以不回溯 sum |
如果你写成 sum += i |
一定要 sum -= i 回溯 |
| 一致性风格建议 | 尽量保持所有回溯变量都有明确的前进和撤销逻辑，代码更安全易读 ✅ |
剪枝操作
class Solution {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
backTracking(n, k, 1, 0);
return result;
}
private void backTracking(int targetSum, int k, int startIndex, int sum) {
// 减枝
if (sum > targetSum) {
return;
}
if (path.size() == k) {
if (sum == targetSum) result.add(new ArrayList<>(path));
return;
}
// 减枝 9 - (k - path.size()) + 1
for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
path.add(i);
sum += i;
backTracking(targetSum, k, i + 1, sum);
//回溯
path.removeLast();
//回溯
sum -= i;
}
}
}17.电话号码的字母组合
题目链接/文章讲解：代码随想录
视频讲解：还得用回溯算法！| LeetCode：17.电话号码的字母组合_哔哩哔哩_bilibili
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
class Solution {
List<String>res=new ArrayList<>();
StringBuilder path=new StringBuilder();
Map<Character,String>map=new HashMap<>();//注意接口和实现类，存储映射关系
public List<String> letterCombinations(String digits) {
map.put('2',"abc");
map.put('3',"def");
map.put('4',"ghi");
map.put('5',"jkl");
map.put('6',"mno");
map.put('7',"pqrs");
map.put('8',"tuv");
map.put('9',"wxyz");
back( digits,0);
return res;}//不能有嵌套类
public void back(String digits,int index)
{
if(digits==null||digits.length()==0)return;
if(path.length()==digits.length())
{
res.add(path.toString());//加入的是字符串的副本
return;
}
String letters=map.get(digits.charAt(index));
for(char a:letters.toCharArray())
{
path.append(a);
back(digits,index+1);
path.deleteCharAt(path.length()-1);
}
}
}注意点：java中为空是null
| 用于哪种对象 | 方法 | 说明 | 示例 |
|---|---|---|---|
数组（如 int[], char[]） |
.length ✅ |
属性，不是方法，没有括号 | arr.length |
| String | .length() ✅ |
是方法，有括号 | "abc".length() |
| ArrayList / LinkedList | .size() ✅ |
是方法，有括号 | list.size() |
| StringBuilder / StringBuffer | .length() ✅ |
是方法，有括号 | sb.length() |
只记一点：数组用 .length，集合用 .size()，字符串相关用 .length()。
StringBuilder.toString()非常常用，用于拼接完字符串后转换成真正的字符串。
String letters 在for循环的前面，是因为在第一个字符串中选一个，然后在第二个字符串中选一个，再拼接