算法学习（9）：LeetCode刷题之回溯算法

算法学习（9）：LeetCode刷题之回溯算法 前言

算法的实现依赖于深度优先搜索DFS，DFS算法尽可能深的搜索某一条路径，直到到达边界，而回溯算法在DFS算法的基础上强调了回退 *** 作，即回溯法采用尝试的思想，分步解决问题，当发现现有的分步结果不能得到正确的结果，它将取消上一步的选择，再通过其他可能的分步继续尝试。

回溯算法，其实还是一棵树的遍历过程。整个回溯过程涉及到3个方面：
1、路径：即已经做出的选择。
2、选择列表：即当前可以做的选择。
3、结束条件：已经符合条件，无法继续选择。

回溯算法通常用于求解一个问题的所有解，如排列、组合、子集等问题。算法模板如下：

result = []
void dfs(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        dfs(路径, 选择列表)
        撤销选择

根据上面这个模板，我们可以写出一道题目：给你一个数组nums，输出数组中所有元素可以组成的排列，其中nums中的元素可以重复选择。

class Solution {
    private List> res = new ArrayList<>();
    public List> permute(int[] nums) {
        List path = new ArrayList<>();
        dfs(nums, path);
        return res;
    }

	// nums就是选择列表，path就是路径
    private void dfs(int[] nums, List path) {
    	// 结束条件
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path)); // java是值传递，需要重新构造List对象
            return;
        }
		// 选择
        for (int i = 0; i < nums.length; i++) {
        	 // 先选择当前元素加入到路径
	         path.add(nums[i]);
	         System.out.println("递归：" + path); // 输出看过程
	         // 递归
	         dfs(nums, path);
			 // 递归后撤销选择，即将最后一个加进来的元素删除
	         path.remove(path.size() - 1);
	         System.out.println("回溯：" + path); // 输出看过程
        }
    }
}

得到的结果是：

[[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3],[2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3],[3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]]

控制台打印信息：

递归：[1]
递归：[1, 1]
递归：[1, 1, 1]
回溯：[1, 1]
递归：[1, 1, 2]
回溯：[1, 1]
递归：[1, 1, 3]
回溯：[1, 1]
回溯：[1]
递归：[1, 2]
递归：[1, 2, 1]
回溯：[1, 2]
递归：[1, 2, 2]
回溯：[1, 2]
递归：[1, 2, 3]
回溯：[1, 2]
回溯：[1]
递归：[1, 3]
递归：[1, 3, 1]
回溯：[1, 3]
递归：[1, 3, 2]
回溯：[1, 3]
递归：[1, 3, 3]
回溯：[1, 3]
回溯：[1]
回溯：[]
递归：[2]
递归：[2, 1]
递归：[2, 1, 1]
回溯：[2, 1]
递归：[2, 1, 2]
回溯：[2, 1]
递归：[2, 1, 3]
回溯：[2, 1]
回溯：[2]
递归：[2, 2]
递归：[2, 2, 1]
回溯：[2, 2]
递归：[2, 2, 2]
回溯：[2, 2]
递归：[2, 2, 3]
回溯：[2, 2]
回溯：[2]
递归：[2, 3]
递归：[2, 3, 1]
回溯：[2, 3]
递归：[2, 3, 2]
回溯：[2, 3]
递归：[2, 3, 3]
回溯：[2, 3]
回溯：[2]
回溯：[]
递归：[3]
递归：[3, 1]
递归：[3, 1, 1]
回溯：[3, 1]
递归：[3, 1, 2]
回溯：[3, 1]
递归：[3, 1, 3]
回溯：[3, 1]
回溯：[3]
递归：[3, 2]
递归：[3, 2, 1]
回溯：[3, 2]
递归：[3, 2, 2]
回溯：[3, 2]
递归：[3, 2, 3]
回溯：[3, 2]
回溯：[3]
递归：[3, 3]
递归：[3, 3, 1]
回溯：[3, 3]
递归：[3, 3, 2]
回溯：[3, 3]
递归：[3, 3, 3]
回溯：[3, 3]
回溯：[3]
回溯：[]

整个回溯的过程形成了下面这样一颗树，下面的leetcode题目都是以这个回溯过程为基础的，只不过是根据题意加入了一些剪枝的 *** 作。

正文 1、LeetCode No.46 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

这道题根据输入示例可以画出下面这颗决策树，站在图中的每个节点上，都将面临选择。结合上面说的3个概念，如果你首先选择了1，那么[1]就是路径，记录了你已经做过的选择，[2、3]就是选择列表，表示你当前可以做的选择，结束条件就是遍历到了树的底层。

这道题目相当于在前言中的算法模板上进行剪枝，怎么剪枝的呢？就是上一层已经选择过了一个数后，下一层这个数就不能再选了。比如上一层已经选择过了2，下一层就不能再选2了，只能在1、3中选。如果已经选择了2、1，最后一层就只能选择3了。那么要怎么控制呢？答案是增加一个boolean数组，记录回溯过程中每个元素的遍历情况，如果当前元素被遍历到，就将boolean数组对应位置置为true，下一层递归访问的时候，遇到该位置是true，就不会访问该位置的元素了，递归完了之后，再把boolean数组该位置置为false，供之后的遍历用到。

解题代码：

class Solution {
    private List> res = new ArrayList<>();
    public List> permute(int[] nums) {
        List path = new ArrayList<>();
        // boolean数组记录nums数组每个位置被访问过的情况
        boolean[] used = new boolean[nums.length];
        dfs(nums, path, used);
        return res;
    }

    private void dfs(int[] nums, List path, boolean[] used) {
    	// 终止条件是path长度和nums长度一样
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
		// 求全排列递归需要遍历整个数组，
        for (int i = 0; i < nums.length; i++) {
        	// 每次递归需要剪枝，即判断元素是否访问过
            if (!used[i]) {
                path.add(nums[i]); // 路径加入元素
                used[i] = true; // 将元素标记为已访问
                //System.out.println("递归：" + path); // 看递归过程
                dfs(nums, path, used); // 递归

                path.remove(path.size() - 1); // 回溯过程需要取消当前的选择
                //System.out.println("回溯：" + path); // 看回溯过程
                used[i] = false; // 将元素标记解除
            }
        }
    }
}