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