回溯算法

概述

废话不多说，直接上回溯算法框架。解决⼀个回溯问题，实际上就是⼀个决 策树的遍历过程。你只需要思考 3 个问题：

1、路径：也就是已经做出的选择。

2、选择列表：也就是你当前可以做的选择。

3、结束条件：也就是到达决策树底层，⽆法再做选择的条件。

result = []
    def backtrack(路径, 选择列表):
        if 满⾜结束条件:
        result.add(路径)
        return
        for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

其核⼼就是 for 循环⾥⾯的递归，在递归调⽤之前「做选择」，在递归调⽤ 之后「撤销选择」，特别简单。

什么叫做选择和撤销选择呢，这个框架的底层原理是什么呢？下⾯我们就通 过「全排列」这个问题来解开之前的疑惑，详细探究⼀下其中的奥妙！

注意： 回溯算法的核心操作，就是 撤销选择

全排列问题

我们在⾼中的时候就做过排列组合的数学题，我们也知道 n 个不重复的 数，全排列共有 n! 个。

[图片上传失败...(image-32d13-1646308220929)]

PS：为了简单清晰起⻅，我们这次讨论的全排列问题不包含重复的数字。

转换成代码语言 =》 //计算 [1,2,3] 全排列 多少种?并且把所有的排练情况 输出

public class Test {
    // 存储 所有排列的情况，存放到list
    public static List<List<Integer>> res = new LinkedList<>();

    public static void main(String[] args) {
            //计算 [1,2,3] 全排列 多少种?并且把所有的排练情况 输出
       int[] nums = {2,3};
        List<List<Integer>> premute = premute(nums);
        System.out.println(premute);

    }

    public static List<List<Integer>> premute(int[] nums) {
        //记录【路径】
        LinkedList<Integer> track = new LinkedList<>();
        //回溯
        backtrack(nums, track);
        return res;
    }
    // 路径：记录在 track 中
    // 选择列表：nums 中不存在于 track 的那些元素
    // 结束条件：nums 中的元素全都在 track 中出现
    public static void backtrack(int[] nums, LinkedList<Integer> track) {
        //【触发结束条件】;
        if(track.size() == nums.length) {
            res.add(new LinkedList<>(track));//将一种排列，存放到链表前面
        }
        //【遍历路径选择】
        for(int i = 0; i < nums.length; i ++) {
            //【排除不合法的】
            if(track.contains(nums[i])) continue;
            //【做选择】，剩下选择一个
            track.add(nums[i]);
            //【递归】
            backtrack(nums, track);
            //【取消选择】就是回溯核心 ： 以一个完整的排列，把完整队列，最后一个位置后退，重新选择
            // 相当于 回退到选择最后一条路
            track.removeLast();
        }

    }

[图片上传失败...(image-e89e60-1646308220929)]

N 皇后问题

这个问题很经典了，简单解释⼀下：给你⼀个 N×N 的棋盘，让你放置 N 个 皇后，使得它们不能互相攻击。 PS：皇后可以攻击同⼀⾏、同⼀列、左上左下右上右下四个⽅向的任意单 位。