几道入门的回溯题 | LeetCode
几道入门的回溯题 | LeetCode
“回学校后发现大家都在不停的卷，而自己本周只写了没几道力扣题目... ”
这周写的几道题整体上都是回溯类型的，也都是些入门级的回溯问题。整体有一套回溯的模板，周末了做个简单的总结记录，也是为了“交作业”哈。
关于回溯自己之前转载了一篇大神的文章：
回溯详解（强推） liweiwei1419，公众号：做棵大树回溯算法入门级详解 | 优秀文章
有兴趣的可以看看。
LC22. 括号生成
“数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 ”
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
当时的想法：
- 定义返回类型 List 这个不管什么时候肯定是需要返回值的
- 因为题目中的这个涉及到回退，所以我们单独定义一个函数来进行 回溯 操作的处理
Java中因为引用对象都是传递的内存地址，所以我们在定义函数的时候直接放进去即可；另外题目中涉及到有效的括号组合 所以我们应该把判断有效用的参数放进方法里，另外将我们当前的状态也就是目前的字符串要放到参数里，因为它是我们的主角，要进行检查和修改的参数。
那怎么判断是否有效呢？
这时候就可以把回溯的函数头定义出来了
process(List<String> res, String str, int left, int right, int n)- 左括号和对数比较，少了，则说明不够
- 左括号个数和右括号个数比较，确定有没有正确的闭合。
- 思考该怎么记录状态，什么时候符合返回值的需要
当
str的长度达到了对数的两倍（正确的长度）我们就可以把它记录到返回值中了。因为String是final修饰的所以我们直接add()就行。 - 状态什么时候回溯 然后因为左括号在左，也就是先出现的，所以我们把左括号的逻辑放在右括号的前边。而回溯的代码就是把状态转变为前一个状态，对于字符串而言，就是删除最后一个添加的字符。
主要是这几个步骤吧，我们就可以编写了。
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
// 回溯
process(res, "", 0, 0, n);
return res;
}
// 记录，字符串，左括号数量，右括号数量，一共几对
public void process(List<String> res, String str, int left, int right, int n){
if(str.length() == n * 2){
// 长度够了
res.add(str);
return;
}
if(left < n){
// 左括号不够
str += "(";
process(res, str, left + 1, right, n);
// 回复之前状态
str = str.substring(0, str.length()-1);
}
if(left > right){
// 没有全部闭合
str += ")";
process(res, str, left, right + 1, n);
// 回复之前状态
str = str.substring(0, str.length()-1);
}
}
}
LC39. 组合总和
给定一个无重复元素的数组 candidates和一个目标数 target，找出 candidates中所有可以使数字和为 target的组合。
candidates中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1：
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]
示例 2：
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
[2,2,2,2],
[2,3,3],
[3,5]
]
当时的想法：
整体和上一题实际上是一样的，具体不一样的点就是：这个问题涉及到的只有一个需要进行记录的点，就是list符合不符合，而上一题进行判断，需要对括号的个数写两个判断逻辑。
方法定义的时候，我们也要考虑到：返回值、记录值、中间值/参考值、下一个开始点（主要涉及到同一个值能不能呗重复使用）。
然后还要注意，因为 backtrace 一般都会涉及到递归结构，所以出口的定义也很重要，很多时候可以避免重复添加。
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> list = new ArrayList<>();
findResult(res, list, candidates, target, 0);
return res;
}
public void findResult(List<List<Integer>> res, List<Integer> list, int[] candidates, int target, int begin){
if(begin == candidates.length || target < 0) return;
if(target == 0){
// 根据条件的取值范围知，当target == 0 已找到
res.add(new ArrayList(list));
return;
}
for(int left = begin; left < candidates.length; left++){
list.add(candidates[left]); // 添加进去
// target - candidate[left] 为更新要查找的值，同“两/三数之和”一样
findResult(res, list, candidates, target - candidates[left], left);
list.remove(list.size() - 1);
}
}
// public boolean notAdded(List<Integer> list){
// // 去重
// }
}
LC40.组合总和II
这道题同上一题相同，唯一区别在于：candidates 中的每个数字在每个组合中只能使用一次。
这个在写的时候因为这个条件提错了三次。。。
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> list = new ArrayList<>();
Arrays.sort(candidates);
backtrace(res, list, candidates, target, 0);
return res;
}
public void backtrace(List<List<Integer>> res, List<Integer> list, int[] candidates, int target, int index){
// 因为往后移动了一位，避免重复使用同一数字，所以 index 要用 > 否则最后一个下标的递归没法进行检查
if(target < 0 || index > candidates.length) return;
if(target == 0){
if(!res.contains(new ArrayList(list)))
// 为了去重
res.add(new ArrayList(list));
return;
}
for(int i = index; i<candidates.length; i++){
list.add(candidates[i]);
backtrace(res, list, candidates, target - candidates[i], i+1);
list.remove(list.size() - 1);
}
}
}
LC797. 所有可能的路径
给一个有 n 个结点的有向无环图，找到所有从 0 到 n-1 的路径并输出（不要求按顺序）
二维数组的第 i 个数组中的单元都表示有向图中 i 号结点所能到达的下一些结点（译者注：有向图是有方向的，即规定了 a→b 你就不能从 b→a ）空就是没有下一个结点了。
示例 1：
输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
这是一条图的路径问题，考虑到的应该也是深度遍历的思想，同时题目要求 0 -- n-1 也指定了结束条件，最开始写时候忽略了，我以为是要所有的路径呢。
那么思路也是相同的，我们按照上述的来进行写即可。
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> item = new ArrayList<>();
item.add(0); // 添加起始点
backtrace(res, item, graph, 0);
return res;
}
public void backtrace(List<List<Integer>> res, List<Integer> item, int[][] graph, int currentNode){
int[] canReach = graph[currentNode]; // 当前点可到达的点
if(currentNode == graph.length - 1){
res.add(new ArrayList(item)); //最后一个节点
return;
}
for(int i = 0; i < canReach.length; i++){
item.add(canReach[i]);
backtrace(res, item, graph, canReach[i]); // 根据当前点延伸到可以到达的点
item.remove(item.size() - 1);
}
}
}
相关的还有 子集问题等等
End
为什么说这是回溯问题的入门呢，因为我们从题目中可以看到，他们的解题结构都是一样的，大致可以概括为以下的代码结构：
主方法{
返回值
填充值
回溯方法(返回值，填充值，状态记录相关参数...);
return 返回值；
}
回溯方法{
// 状态核验，是否符合合法条件
if(不符合合法条件) return;
if(符合返回条件) 添加进返回值;
进入递归状态，一般会涉及到循环
循环语句
递归调用回溯方法(返回值，填充值，更新后的状态记录参数)
消除上次修改的状态，完成回溯
循环结束
涉及多个状态的可能要写不只一个回溯的代码段，视情况而定。
}
但是再深一点的回溯问题，可能不会这么容易的让我们找到 该怎么记录状态 以及 什么时候实现状态回退，所以上边的题目应该只能算我们入门回溯的几道入门题目了，这里也就不再班门弄斧了，大家可以去LeetCode的回溯专题下去做一下相关题目。
腾讯云开发者
