backtrack 回溯算法
先做决定，然后撤回 , 就是一个决策树的遍历
需要注意的有三个问题
-
路径
-
选择
-
终止条件
伪码如下:
public void backtrack(路径，选择列表){ if (终止条件){ add(路径)； return; } for 选择 in 列表 { 做选择； backtrack(路径，选择列表); 撤回； } }
而且不管怎么优化，都符合回溯框架，而且时间复杂度都不可能低于 O(N!)，因为穷举整棵决策树是无法避免的。这也是回溯算法的一个特点，不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高
46. 全排列 题目要求不含重复数字，所以我们还需要注意不符合的选择
class Solution {
public List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> permute(int[] nums){
LinkedList<Integer> track = new LinkedList<>();
backtrack(nums , track);
return res;
}
private void backtrack(int[] nums, LinkedList<Integer> track) {
// 触发结束条件
if (track.size() == nums.length) {
res.add(new LinkedList(track));
return;
}
for (int i = 0; i < nums.length; i++) {
// 排除不合法的选择
if (track.contains(nums[i]))
continue;
// 做选择
track.add(nums[i]);
// 进入下一层决策树
backtrack(nums, track);
// 取消选择
track.removeLast();
}
}
}
47. 全排列 II 而在47中，是包含了重复数字
class Solution {
boolean[] record;
List<List<Integer>> ans = new LinkedList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
int n = nums.length;
if (n == 0){
return ans;
}
//剪枝前需排序
Arrays.sort(nums);
LinkedList<Integer> track = new LinkedList<>();
record = new boolean[n];
backtrack(nums , track);
return ans;
}
private void backtrack(int[] nums , LinkedList<Integer> list){
if (nums.length == list.size()){
ans.add(new LinkedList<>(list));
return;
}
for (int i = 0; i < nums.length; i++) {
if (record[i]){
continue;
}
//剪枝，!record[i - 1]为顺序剪枝，record[i - 1]为倒序剪枝
if (i > 0 && nums[i] == nums[i - 1] && !record[i - 1]) {
continue;
}
record[i] = true;
list.add(nums[i]);
backtrack(nums , list);
record[i] = false;
list.removeLast();
}
}
}