@[toc]
一、回溯算法是什么?
结论:==回溯 = 穷举==
解决一个回溯问题,实际上就是一个决策树的遍历过程
- 路径:就是已经做出的选择
- 选择列表:就是你当前可以做出的选择
- 结束条件:就是base case条件,也就是临界条件
二、框架如下:
==框架如下:==
result = []
def backtrack(路径,选择列表) {
if 满足结束条件 :
result.add(路径)
return
for 选择 in 选择列表
做选择
backtrack(路径,选择列表)
撤销选择
}
==举例:经典回溯算法问题:全排列问题==
public class TestNode {
private static List<List<Integer>> res = new LinkedList<>();
public static void main(String[] args){
//问题2.1:全排列问题
permute(new int[]{1,2,3});
res.stream().forEach(item -> System.out.print(item + " "));
}
/**
* 问题2.1:全排列问题,输入一个数组,输出所有全排列顺序
* 框架:路径:记录在track中
* 选择列表:nums中不存在于track的那些元素
* 结束条件:nums中元素全部在track中出现
* @param nums 数组
* @return list
*/
public static List<List<Integer>> permute(int[] nums) {
//记录“路径”
LinkedList<Integer> track = new LinkedList<>();
backtrack(nums, track);
return res;
}
public static void backtrack(int[] nums, LinkedList<Integer> track) {
//base case
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();
}
}
==输出结果==
[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]