理论基础
什么是回溯法
回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
回溯是递归的副产品，只要有递归就会有回溯。
所以以下讲解中，回溯函数也就是递归函数，指的都是一个函数。
回溯法的效率
回溯法的性能如何呢，这里要和大家说清楚了，虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法。
因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。
回溯法解决的问题
回溯法，一般可以解决如下几种问题：
- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等
77. 组合
题目
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2 输出： [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4], ]
示例 2：
输入：n = 1, k = 1 输出：[[1]]
提示：
1 <= n <= 201 <= k <= n
题目解析
代码详解：
-
全局变量：
path：存储当前正在生成的组合，使用LinkedList方便增删元素。result：存储所有符合条件的组合结果，是一个二维列表。
-
combine方法：- 功能：入口方法，调用
backtrace开始回溯，生成组合。 - 返回值：返回所有可能的组合，即
result。
- 功能：入口方法，调用
-
backtrace方法：-
功能：递归生成从 1 到
n的所有长度为k的组合。 -
参数说明：
n：数字范围的上限。k：组合的长度。startindex：当前递归中起始选择的数字，避免重复选择。
-
回溯逻辑：
- 递归终止条件：当当前路径长度
path.size()等于k，将当前组合加入结果集result，然后返回。 - 递归核心：
- 遍历从
startindex到n的数字。 - 将当前数字
i加入路径path。 - 递归调用
backtrace，将下一个数字的起始点设为i+1。 - 回溯：移除当前路径中的最后一个数字，恢复状态。
- 遍历从
- 递归终止条件：当当前路径长度
-
-
时间复杂度：每个组合需要 O(k)的时间拷贝到结果中，因此总时间复杂度为 O(k⋅C(n,k))
-
空间复杂度：
- 递归深度为 kkk，路径
path的空间复杂度为 O(k)O(k)O(k)。 - 结果集
result的空间复杂度为 O(C(n,k))O(C(n, k))O(C(n,k))。
- 递归深度为 kkk，路径
class Solution {List <Integer>path=new LinkedList<>();//记录路径List<List<Integer>> result=new ArrayList<>();//记录结果集public void backtrace(int n,int k,int startindex){if(path.size()==k){//终止条件result.add(new ArrayList<>(path));return;}for(int i=startindex;i<=n;i++){//回溯逻辑path.add(i);backtrace(n,k,i+1);path.removeLast();}}public List<List<Integer>> combine(int n, int k) {backtrace(n,k,1);return result;}
}优化
剪枝优化分析：
普通遍历范围：
在没有剪枝的情况下，for 循环会遍历完整的范围 [startIndex, n]。
剪枝后的范围：
通过计算 n - (k - path.size()) + 1，调整了遍历的结束范围：
k - path.size()：表示还需要选取的元素个数。n - (k - path.size()) + 1：保证剩余元素的数量足够填满路径。
剪枝的作用：
当剩余未选的元素数量不足时，直接停止循环，避免无效的递归和计算。例如：
- 假设
n = 5, k = 3，当前路径已经选了 1 个元素，即path.size() = 1。 - 剩余需要选取的元素数量为
k - path.size() = 2。 - 此时的遍历范围变为： 范围=[startIndex,n−(k−path.size())+1]=[startIndex,5−2+1]=[startIndex,4]
- 如果从
startIndex = 5开始遍历，会导致剩余元素不足以构成一个长度为 3 的组合，从而浪费时间。
完整逻辑示例：
假设 n = 5, k = 3：
无剪枝：
- 假设当前路径
path = [1]。 - 遍历范围为
[2, 5]，会继续尝试[1, 2, 3],[1, 2, 4],[1, 2, 5]等所有情况。
剪枝后：
- 当前路径
path = [1]，还需要选取2个元素。 - 剪枝调整遍历范围为
[2, 4]（因为从 5 开始无法满足k = 3的组合）。 - 遍历结束后直接回溯，避免了对
[1, 5]这种无效路径的递归。
class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> combine(int n, int k) {combineHelper(n, k, 1);return result;}/*** 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex* @param startIndex 用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,...,n] ）。*/private void combineHelper(int n, int k, int startIndex){//终止条件if (path.size() == k){result.add(new ArrayList<>(path));return;}for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){path.add(i);combineHelper(n, k, i + 1);path.removeLast();}}
}216. 组合总和 III
题目
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
输入: k = 3, n = 7 输出: [[1,2,4]] 解释: 1 + 2 + 4 = 7 没有其他符合的组合了。
示例 2:
输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]] 解释: 1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 没有其他符合的组合了。
示例 3:
输入: k = 4, n = 1 输出: [] 解释: 不存在有效的组合。 在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
提示:
2 <= k <= 91 <= n <= 60
题目解析
弄懂了组合这道题，那么本题就没什么难度，只是加了一个判断语句，判断path路径的总和是否为目标值，代码如下：
class Solution {List<Integer>path=new LinkedList<>();List<List<Integer>>result=new ArrayList<>();public void backtrace(int n,int k,int startindex){if(path.size()==k){int sum=0;for(int i=0;i<k;i++){sum+=path.get(i);}if(sum==n)result.add(new ArrayList<>(path));return;}for(int i=startindex;i<=9-(k-path.size())+1;i++){//用了剪枝path.add(i);backtrace(n,k,i+1);path.removeLast();}}public List<List<Integer>> combinationSum3(int k, int n) {backtrace(n,k,1);return result;}
}17. 电话号码的字母组合
题目
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = "" 输出：[]
示例 3：
输入：digits = "2" 输出：["a","b","c"]
提示：
0 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
题目解析
代码详解：
-
全局变量：
path：存储当前正在生成的组合，使用 StringBulider方便增删元素。result：存储所有符合条件的组合结果，是一个String列表。
-
letterCombinations方法：- 功能：入口方法，调用
backtrace开始回溯，生成组合。 - 返回值：返回所有可能的组合，即
result。
- 功能：入口方法，调用
-
backtrace方法：-
功能：递归生成从 所有可能的组合。
-
参数说明：
- digits：按键String。
index：当前递归中起始选择的索引，避免重复选择。
-
回溯逻辑：
- 递归终止条件：当当前索引等于digits字符串长度，将当前组合加入结果集
result，然后返回。 - 递归核心：
- 遍历从 当前按键指示的字符。
- 将当前字符letters.charAt(i)加入路径
path。 - 递归调用
backtrace，将下一个字符的索引设为 index+1。 - 回溯：移除当前路径中的最后一个字符，恢复状态。
- 递归终止条件：当当前索引等于digits字符串长度，将当前组合加入结果集
-
-
时间复杂度：
- 假设输入字符串长度为 n，每个数字对应最多 4 个字母，总的组合数为 O(4^n)。
- 每次递归操作涉及字符串拼接或回溯，时间复杂度为O(n⋅4^n) 。
-
空间复杂度：
- 递归深度为 O(n)，回溯中字符串路径
path的空间为 O(n)。 - 总空间复杂度为 O(n)。
- 递归深度为 O(n)，回溯中字符串路径
class Solution {List<String> num = new ArrayList<>();List<String> result = new ArrayList<>();StringBuilder path = new StringBuilder();public void backtrace(String digits, int index) {// 终止条件：遍历完整个数字if (index == digits.length()) {result.add(path.toString());return;}// 当前数字对应的字母集合int number = digits.charAt(index) - '2';String letters = num.get(number);for (int i = 0; i < letters.length(); i++) {// 添加当前字母到路径path.append(letters.charAt(i));// 递归处理下一个数字backtrace(digits, index + 1);// 回溯：恢复状态path.deleteCharAt(path.length() - 1);}}public List<String> letterCombinations(String digits) {if (digits == null || digits.isEmpty()) {return result;}// 初始化数字与字母映射num.add("abc");num.add("def");num.add("ghi");num.add("jkl");num.add("mno");num.add("pqrs");num.add("tuv");num.add("wxyz");// 开始回溯backtrace(digits, 0);return result;}
}