回溯到底怎么用？
回溯的适用范围
回溯法，一般可以解决如下几种问题：
- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等
三大关键点
回溯法解决的问题都可以抽象为树形结构
**集合的大小就构成了树的宽度，递归的深度，都构成的树的深度**。
递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）
回溯模板就是递归三部曲
遇到题目的解法
首先，一定要分类是哪类题。组合、分割、子集还是棋盘…
组合
最经典的题目
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。 示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
在没有学习回溯之前我们可能就是只会n层for循环来解决这种题
在学习了回溯之后，我们就可以先进行画图分析【图片来自代码随想录: 连接代码随想录 (programmercarl.com)】
思路很显然就是递归三部曲
- 递归返回值、参数
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combine(int n, int k) {
//....
combineHelper(....);
}
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();
}对于这种类型的题思路我们需要很清晰
因为这道题他需要的是【1 … n 中所有可能的 k 个数的组合】那么其中的重点我们就可以get到
- 组合！！！
- 给出的元素不重复
- 需要的是k个数的组合
- 根据实例给出的答案可以得出【各个集合不重复】
由上述的get点，我们就可以是实现我们的思路了。
组合: 那么就是 使用回溯算法
给出的元素不重复: 不需要我们自己手动去重
得出的各个集合不重复: 需要使用index指针来移动递归的位置
组合Ⅱ
根据上一题的思路，我们再来看看这道题的解法
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。 说明：
- 所有数字都是正整数。
- 解集不能包含重复的组合。
示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]] 示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
get关键点
- 组合
- 解集不能重复
- 给出的元素不重复
- 所有相加之和为 n 的 k 个数的组合
根据上面我们罗列的要求，我们就可以实现思路了。
组合: 那么就是 使用回溯算法
给出的元素不重复: 不需要我们自己手动去重
解集不能包含重复的组合: 使用index指针来移动递归的位置
题目中需要得是【和为n的k个数】
那么就需要将得出的数进行相加，如果和为 n 那么就将得出集合加入结果集中
此时我们传参就不能再向之前那样了
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 index, int sum) {
}我们需要传入求和的参数sum，来对每一个得出的元素进行相加
//单层递归的逻辑
for(int i = index; i < k ;i++ ){
sum += i;
path.add(i);
backTracking(targetSum,k, i + 1,sum);
//回溯
sum-=i;
path.remove(path.size() - 1);
}组合总和Ⅱ
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用一次。 说明： 所有数字（包括目标数）都是正整数。解集不能包含重复的组合。
- 示例 1:
- 输入: candidates = [10,1,2,7,6,1,5], target = 8,
- 所求解集为
[ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
- 示例 2:
- 输入: candidates = [2,5,2,1,2], target = 5,
- 所求解集为:
[ [1,2,2], [5] ]
get关键点
- 组合
- 解集不能重复
给出的元素重复- 所有数组中元素之和为 target的组合
重点
给出的元素重复
因为给出的元素重复，而我们的结果集中不能有重复的组合，那么我们单层递归的逻辑就需要发生一些改变
如图:【图片来自代码随想录: 代码随想录 (programmercarl.com)】
- 首先我们需要将题目中给出的数组进行排序，让相同的元素处于相邻的位置
- 借用used数组，对已经用过的数组中的元素进行标记
- 判断如果
i > 0 && nums[i] == nums[i-1] && used == 0， 那么就可以说明相邻的数组是重复的，只需要跳过本次循环即可。 - 对于树枝循环，如果数组使用过了，那么就设置对应的used[i] == 1; 当一个树枝走到头 ，也就是到达叶子节点。那么就进行回溯，将used数组中设置的1清 0 。调用下一个树枝时重新进行设置used = 1 。进入③再次进行判断
- 直到index指向数组的最后一个元素。那么递归就结束了
对应的实现代码
class Solution {
LinkedList<Integer> path = new LinkedList<>();
List<List<Integer>> ans = new ArrayList<>();
//2. 借用used数组，对已经用过的数组中的元素进行标记
int[] used;
int sum = 0;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
used = new int[candidates.length];
// 1. 为了将重复的数字都放到一起，所以先进行排序
Arrays.sort(candidates);
backTracking(candidates, target, 0);
return ans;
}
private void backTracking(int[] candidates, int target, int startIndex) {
if (sum == target) {
ans.add(new ArrayList(path));
}
for (int i = startIndex; i < candidates.length; i++) {
//对于大于target的元素不进行递归，降低时间复杂度
if (sum + candidates[i] > target) {
break;
}
//3. 出现重复节点，同层的第一个节点已经被访问过，所以直接跳过
if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == 0) {
continue;
}
//4. 对于树枝上使用过的元素进行赋值为 1
used[i] = 1;
sum += candidates[i];
path.add(candidates[i]);
// 5. 每个节点仅能选择一次，所以从下一位开始
backTracking(candidates, target, i + 1);
used[i] = 0;
sum -= candidates[i];
path.remove(path.size() - 1);
}
}
}切割字符串
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。 返回 s 所有可能的分割方案。 示例: 输入: “aab” 输出: [ [“aa”,”b”], [“a”,”a”,”b”] ]
get关键点
- 分割成一些字符串
- 每个字符串都是回文串
根据上面的要求，我们首先能确定的是这道题用回溯算法做
那么就可以将这道题抽象成为一个树结构
如图:【图片来自代码随想录: 代码随想录 (programmercarl.com)】
其次，我们需要判断我们切割的字符字串是不是回文串
判断我们就可以封装成为一个函数
//判断是否是回文串
private boolean isPalindrome(String s, int startIndex, int end) {
for (int i = startIndex, j = end; i < j; i++, j--) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
}
return true;
}对于切割字符串，因为我们已经确定这道题使用回溯算法做，那么就可以用递归三部曲
- 确定递归参数，返回值
List<List<String>> res = new ArrayList<>();
List<String> path = new ArrayList<>();
public List<List<String>> partition(String s) {
backTracking(s, 0);
return res;
}
public void backTracking(String s ,int index){
}
- 递归终止条件
只有切割完毕才会收集
if(index >= s.length()){
res.add(new ArrayList<>(path));
return;
}- 单层递归逻辑
for(int i = index ; i < s.length() ; i++){
//切割字符串，然后判断字符串是否是回文串， 如果不是，那么就跳过本次的循环，直接进行下一轮
String str = s.substring(index,i);
if(isPalindrome(str,index,i + 1)){
path.add(str);
}else{
continue;
}
backTracking(s,i+1);
path.remove(path.size() - 1);
}子集问题
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 说明：解集不能包含重复的子集。 示例: 输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
腾讯云开发者
