【算法】回溯算法

回溯算法

什么是回溯

人生无时不在选择。在选择的路口，你该如何抉择 .....

回溯： 是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

回溯，计算机算法，回溯法也称试探法，它的基本思想是：从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法”。--百度百科

一个例子看回溯

给下图的图顶点进行三种颜色着色（红、黄、蓝)

要求:

1. 每个顶点的颜色只能从红、黄、蓝中选一个种。

2. 相邻的两种颜色不能为同一种颜色。

思考方式

暴力推测，查找各种可能...

树型策略

暴力查找结果(从上向下[第n=1行开始]，从左边开始):

1. n=1,先取红，n=2取红

1. [红、红、红], [红,红,黄],[红，红,蓝]; [红,黄, 红],[红，黄，黄]，[红，黄，蓝]；[红，蓝，红],[红，蓝，黄]，[红，蓝，蓝]

2. n=1, n=2取黄

3. n=2, n=3,取蓝色

1. 回溯到根节点，走n=1，取黄色

回溯的一般规律

我们可以针对以上的找色问题，给出以下的一般的解决方案。

1. 初始化： 初始化变量

2. 找一个合法值，通过遍历(+1/-1)选取所有的可能[可以认为是树的深度]

3. 栈记录

4. 递归调用

5. 回溯已经使用的值

经典题目

全排列

题目

[力扣46] 46. 全排列 - 力扣（LeetCode）

题目描述

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

示例 1：

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

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

解决方案

提交模版

public List<List<Integer>> permute(int[] nums) { ​ }

参考实现

class Solution {
​
    private List<List<Integer>> list = new ArrayList<>();
    private Stack<Integer> stack = new Stack<>();
​
    public List<List<Integer>> permute(int[] nums) {
        boolean[] isUsed = new boolean[nums.length];
        dfs(nums, 0, isUsed);
        return list;
    }
​
    private void dfs(int[] nums, int depth, boolean[] isUsed) {
        if (depth == nums.length) {
            list.add(new ArrayList<>(stack));
            return;
        }
​
        for (int i = 0; i < nums.length; i++) {
            if (isUsed[i]) {
                continue;
            }
            stack.push(nums[i]);
            isUsed[i] = true;
            dfs(nums, depth + 1, isUsed);
            stack.pop();
            isUsed[i] = false;
        }
    }
}

全排列II

题目

[力扣47] 47. 全排列 II - 力扣（LeetCode）

题目描述

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = {1,1,2}
输出：
{
 {1,1,2},
 {1,2,1},
 {2,1,1}
}

示例 2：

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

解题思路

提交模版

public List<List<Integer>> permuteUnique(int[] nums) {   }

参考实现

class Solution {
  private final List<List<Integer>> list = new ArrayList<>();
    private final Stack<Integer> stack = new Stack<>();
    private final Set<List<Integer>> sets = new HashSet<>();
​
​
    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] isUsed = new boolean[nums.length];
        dfs(nums, 0, isUsed);
        list.addAll(sets);
        return list;
    }
​
    /**
     * @param nums
     * @param depth  递归的深度，从底层开始到最后一层
     * @param isUsed 判断当前数据是否使用过
     */
    private void dfs(int[] nums, int depth, boolean[] isUsed) {
        if (depth == nums.length) {
            sets.add(new ArrayList<>(stack));
            return;
        }
​
        Set<Integer> set = new HashSet<>();//记录重复数据
        for (int i = 0; i < nums.length; i++) { //遍历数组
            //数据重复或者使用过则跳过当前数据
            if (isUsed[i] ) continue;
           // set.add(nums[i]); //记录选择的数据
          //  System.out.println("set-->" + set);
            stack.push(nums[i]);
            isUsed[i] = true;
            dfs(nums, depth + 1, isUsed);
            stack.pop();
            isUsed[i] = false;
        }
    }
}

子集问题

题目

[力扣78] 78. 子集 - 力扣（LeetCode）

题目描述

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

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

示例 2：

输入：nums = [0]
输出：[[],[0]]

解题思路

创建策略树

我们会发现出现大量的无效操作数据。对策略树进行"剪枝"处理。

剪枝- 我们“剪掉”了不满足约束条件的搜索分支，避免许多无意义的尝试，从而提高了搜索效率。

提交模版

 public List<List<Integer>> subsets(int[] nums) { }

参考实现

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    Stack<Integer> stack = new Stack<>();
​
    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums, 0);
        return list;
    }
​
    private void dfs(int[] nums, int startIndex) {
​
        list.add(new ArrayList<>(stack));
        if (startIndex >= nums.length) {
            return;
        }
​
        for (int i = startIndex; i < nums.length; i++) {
            stack.push(nums[i]);
            dfs(nums, i + 1);
            stack.pop();
​
        }
    }
}

剪枝优化

class Solution {
    private final List<List<Integer>> list = new ArrayList<>();
    private final List<Integer> stack = new ArrayList<>();
​
    public List<List<Integer>> subsets(int[] nums) {
        boolean[] isUsed = new boolean[nums.length];
        dfs(nums, 0, isUsed);
        return list;
    }
​
    private void dfs(int[] nums, int startIndex, boolean[] isUsed) {
​
        list.add(new ArrayList<>(stack)); //记录扫描的所有节点
        for (int i = startIndex; i < nums.length; i++) {
            if (isUsed[i])
                continue;
            stack.add(nums[i]);
            isUsed[i] = true;
            dfs(nums, i + 1,isUsed);
            stack.remove(stack.size()-1);
            isUsed[i] = false;
​
        }
    }
}

子集II

题目

[力扣90] 90. 子集 II - 力扣（LeetCode）