文章目录
一、回溯算法是什么？
结论：回溯 = 穷举
解决一个回溯问题，实际上就是一个决策树的遍历过程
- 路径：就是已经做出的选择
- 选择列表：就是你当前可以做出的选择
- 结束条件：就是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]
本人其他文章链接
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/106252.html
