回溯的核心思路
回溯算法是一种比较经典的算法思想。它的思想在于：通过枚举法，对所有可能的选择进行遍历。枚举的顺序一般是一条路走到黑，发现黑之后，回退一步，再向前尝试没有走过的路。直到所有的路都尝试过。因此，回溯法也可以理解为是走不通就退一步的枚举方式。
回溯的3个关键在于：
- 一条路走到黑；
- 回退一步；
- 另寻他路；
其中主要又用循环和递归来实现。
- 循环的作用在于另寻他路，可以用来实现选择所有的路径，例如我们走到了选择点，向后的路有条，那么我们就需要把这条路径都选择一次才可以，使用循环就是为了把所有向后的路径都尝试一遍；
- 递归实现的就是一条路走到黑和回退一步。一条路走到黑是指：递归每次向着给出的路径向后继续走了一步。如果将递归放在循环体内，每一次的循环，都会在给出一个路径后，继续沿着这个路径向后递归，直到走到递归的出口。
- 递归从出口出来之后，就会实现回退一步。从出口出来之后，这一层的循环的其他选择就要开始执行，所以会继续执行当前节点的下一条可行路径，然后递归调用，就顺着这条没走过的路径又走了一步。
回溯算法的模板
def dfs():
if (回朔点）：# 这条路走到底的条件。也是递归出口
保存该结果
return
else:
for route in all_route_set : 逐步选择当前节点下的所有可能route
if 剪枝条件：
剪枝前的操作
return #不继续往下走了，退回上层，换个路再走
else：#当前路径可能是条可行路径
保存当前数据 #向下走之前要记住已经走过这个节点了。例如push当前节点
self.dfs() #递归发生，继续向下走一步了。
回朔清理 # 该节点下的所有路径都走完了，清理堆栈，准备下一个递归。例如弹出当前节点
这里的剪枝是指,对于有些情况,再继续往后走也是没有用的,所以可以提前退出。
在这里梳理一下在leetcode上碰到的回溯算法的运用。
子集问题
子集问题一般是求一个N个数的集合里有多少符合条件的子集。而在树形结构中子集问题是要收集所有节点的结果
以下为leetcode上有关子集问题的两道题目：
分析这道题的话，就可以得到如下的树形递归结构，可以直到遍历这个树的时候，把所有节点记录下来，就是要求的子集集合。
所以用Java代码表述就是：
以下使用来选择不同的路径
class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> subsets(int[] nums) {
int n = nums.length;
if(n == 0) {
ans.add(path);
return ans;
}
backtrack(nums, 0, n);
return ans;
}
private void backtrack(int[] nums, int idx, int end) {
ans.add(new LinkedList(path));
if(idx >= end) {
return ;
}
for(int i = idx; i < end; i++) {
path.add(nums[i]);
backtrack(nums, i + 1, end);
path.removeLast();
}
}
}
这道题比起上一题，提到了可能包含重复元素，但是子集本身不能重复，即子集中可以允许有重复元素，但是子集不能重复。所以要考虑怎么在所有的子集中去重。
还是考虑上一题的递归树，对于同一个子集中的重复元素，他们是同一个路径下的重复元素，而对于不同子集，他们是同一个树层上的，所以应该想的是怎么去重同一个节点下后面的选择的去重。
于是考虑先将数组排序，这样相同节点就会在一起，如果当前节点和前面的元素相同，如果继续选择，就会产生相同的一条路径，会导致重复，所以如果和前面的元素相同了，应该考虑剪枝。
class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
if(n == 0) {
ans.add(path);
return ans;
}
backtrack(nums, 0, n);
return ans;
}
private void backtrack(int[] nums, int idx, int end) {
ans.add(new ArrayList(path));
if (idx >= end) {
return ;
}
for(int i = idx; i < end; i++) {
if (i > idx && nums[i] == nums[i - 1]) {
// 同一树层有相同元素
continue;
}
path.add(nums[i]);
backtrack(nums, i + 1, end);
path.remove(path.size() - 1);
}
}
}
排列问题
排列问题的特殊在于同一个集合,如果顺序不一样,也是被视为不同的集合。所以对于每个排列问题，都需要从头开始，这样才能确保搜索了所有路径。
举个栗子：比如求的全排列，可以有和两种，同一个1出现在不同的位置就是不同的排列。
所以对于排列问题，我们不使用来标识当前位置，而使用一个来标识是否使用过当前元素，因为使用过的元素，这个排列里肯定就不能再次使用。
class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
int n = nums.length;
if (n == 0) {
return ans;
}
boolean[] used = new boolean[n];
backtrack(nums, used);
return ans;
}
private void backtrack(int[] nums, boolean[] used) {
if(path.size() == nums.length) {
ans.add(new ArrayList(path));
return ;
}
for(int i = 0; i < nums.length; i++) {
if(used[i]) {
continue;
}
path.add(nums[i]);
used[i] = true;
backtrack(nums, used);
used[i] = false;
path.remove(path.size() - 1);
}
}
}
这道题比起上一题，数组里可能有重复数字，并且全排列不能重复。
这里的去重其实也是涉及了同一树层上的去重。
图中我们对同一树层，前一位（也就是nums[i-1]）如果使用过，那么就进行去重。
class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
int n = nums.length;
if(n == 0) {
return ans;
}
Arrays.sort(nums);
boolean[] used = new boolean[n];
backtrack(nums, used);
return ans;
}
private void backtrack(int[] nums, boolean[] used) {
if(path.size() == nums.length) {
ans.add(new ArrayList(path));
return ;
}
for(int i = 0; i < nums.length; i++) {
if(used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
continue;
}
path.add(nums[i]);
used[i] = true;
backtrack(nums, used);
used[i] = false;
path.remove(path.size() - 1);
}
}
}
