【算法】回溯算法

回溯算法 什么是回溯

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

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

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

一个例子看回溯

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

要求:

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

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

思考方式

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

树型策略

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

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

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

n=1, n=2取黄

n=2, n=3,取蓝色

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

回溯的一般规律

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

初始化： 初始化变量

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

栈记录

递归调用

回溯已经使用的值

经典题目 全排列 题目

[力扣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）