回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
回溯是递归的副产品，只要有递归就会有回溯。
所以以下讲解中，回溯函数也就是递归函数，指的都是一个函数。
- 组合问题：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()) + 1for (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循环的前面，是因为在第一个字符串中选一个，然后在第二个字符串中选一个，再拼接
