@
目录一、回溯算法是什么?
结论:回溯 = 穷举
解决一个回溯问题,实际上就是一个决策树的遍历过程
- 路径:就是已经做出的选择
- 选择列表:就是你当前可以做出的选择
- 结束条件:就是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]
本人其他文章链接
2.BFS(Breath First Search 广度优先搜索)
标签:练习题,LinkedList,nums,track,backtrack,选择,算法,回溯 From: https://www.cnblogs.com/bigcat26/p/18520211