思想
回溯法（back tracking）（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
回溯法解求解问题步骤
- 针对给定问题，定义问题的解空间树；（这一步非常重要！！）
- 确定易于搜索的解空间结构；
- 以深度优先方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；
- 用回溯法求解问题，重点是设计问题的解空间树，其解题过程则是深度遍历解空间树的过程。
注：在回溯法中通常会使用到“递归”和“剪枝”
常用的剪枝函数：用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。
回溯法对解空间做深度优先搜索时，有递归回溯和迭代回溯（非递归）两种方法，但一般情况下用递归方法实现回溯法。
模板
回溯法的一般模板，可以如下所示：
demoMethod() {
//生成回溯结果的存储位置
Object res = new Object();
//边界值判定，比如n == 0之类的。
if() return res;
//回溯递归函数，先写出来占个坑，参数一会儿加。
backTrack();
//返回，程序结束。
return res;
}
backTrack(...args[]) { //参数根据题目实际情况来定，数量一般会在4-5个左右
// 递归的结束条件
if () {
}
//回溯算法的主体，包括前进和回溯，sub是存储结果
for(){
add() // 1.一个解中的某个元素，进行添加;
backTrack(index + 1); // 2.进行深搜，进行到解空间树的下一层
sub.remove(sub.size() - 1); // 3.*回溯到解空间树的上一层
}
}
需要注意的是：
- for循环的次数；：在解空间树种每一层有多少种可能的答案，就要循环多少次。
- 以及递归的结束条件：当达到解空间树的叶子节点，即递归的结束条件一般会跟解空间树的深度有关。
具体我们以下面的例子做讲解：
例子
Leetcode上有很多回溯算法问题。这里用一个leetcode上比较经典的题目来做示例
传送门：https://leetcode-cn.com/problems/permutations-ii/
全排列.png
下面将详细介绍一下解题思路：（此思路适用回溯法80%的题目）：
1.定义问题的解空间树，如下图所示；
2.分析发现，在回溯函数中循环的次数应该是每次剩下数组的长度（因为每次都会存储一个值）；如下图中横框框住的元素个数，第一层3种情况；第二层2种情况；第三层1种情况；
3.递归结束条件：当当前的解中的元素经满了（即3个，给定的数组的长度），则跳出本层，回到上层树。
值得注意的是：本题有个要求是，答案不能有重复的。如果不进行剪枝，则会有6个答案，但是如图所示有两处可以剪枝，那剪枝的条件是什么呢？我们发现，只要在每层访问的时候，如果这个节点我们已经访问过了，我们就可以直接跳过，例如：在第一层，第二个的1已经访问过，所以我们可以跳过。因此我们可以在每一层都维护一个已经访问的节点即可。
image.png
解答
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> deque = new LinkedList<>();
if (nums.length == 0) {
return res;
}
for (int i = 0; i < nums.length; i++) {
deque.add(nums[i]);
}
backTrack(res, new ArrayList<>(), deque, nums.length);
return res;
}
/**
*
* @param res - 存储最后的结果，即返回值
* @param curList - 存储当前的值
* @param deque - 解空间树种每一层可能的情况的集合
* @param length - 递归结束条件的长度，即树的深度
*/
private static void backTrack(List<List<Integer>> res, List<Integer> curList, List<Integer> deque, int length) {
if (curList.size() == length) {
res.add(new ArrayList<>(curList));
}
int size = deque.size();
List<Integer> visited = new ArrayList<>();
for (int i = 0; i < size; i++) {
// 剪枝函数
if (visited.contains(deque.get(i))) {
continue;
}
visited.add(deque.get(i));
List<Integer> temp = new ArrayList<>(deque);
curList.add(deque.get(i));
temp.remove(i);
backTrack(res, curList, temp, length);
curList.remove(curList.size() - 1);
}
}
}
网友评论