回溯算法

Java leetcode
数据结构与算法
发布日期:   2022-09-09

4.1 回溯算法解决子集、组合、排列问题

4.1.1 子集

  • 输入一个不包含重复数字的数组，要求算法输出这些数字的所有子集
  • 比如说输入nums = [1,2,3]，应该输出8个子集，包括空集及其本身
  • 第一个解法是利用数学归纳法的思想:假设现在已经知道了规模更小的子问题的结果，如何推到出当前问题的结果?
  • 具体来说就是将nums = [1,2,3]拆分，如果已经知道了[1,2]的子集 ，是否可以推到出[1,2,3]的子集呢?具体地会发现这样一个规律:[1,2,3]的子集就是把[1,2]的子集中的每个集合在添加上3
subset([1,2,3])
= A+ [A[i].add(3) for i = 1...len(A)]
  • 这就是一个典型的递归结构问题，[1,2,3]的子集可以由[1,2]追加得到，[1,2]的子集可以由[1]追加得出,那么base-case就是当输入集合为空的时候，输出子集也就是一个空集
vector<vector<int> > subsets(vector<int>& nums){
    //base-case,返回一个空集
    if(nums.empty()){
        return {{}};
    }
    //把最后一个元素拿出来
    int n = nums.back();
    nums.pop_back();
    //先递归算出前面元素的所有子集
    vector<vector<int>> res =  subsets(nums);
    int size = res.size();
    for(int i = 0;i<size;i++){
        //然后在之前的结果之上累加
        res.push_back(res[i]);
        res.back().push_back(n);
    }
    return res;
}
private List<List<Integer>> ans = new ArrayList<List<Integer>>();

public List<List<Integer>> subsets(int[] nums) {
    dfs(nums.length-1,nums);
    return ans;
}
private List<Integer> copy(List<Integer> raw,int n){
    List<Integer> newList = new ArrayList<>();
    for (Integer id : raw) {
        newList.add(id);
    }
    newList.add(n);
    return newList;
}
//递归计算
private void dfs(int cur,int[] nums){
    if(cur == -1){
        //此时为空集
        ans.add(new ArrayList<>());
        return;
    }
    //先计算出之前所有元素的子集
    int n = nums[cur];
    dfs(cur-1,nums);
    //然后在先前的基础上追加即可
    int size = ans.size();
    for(int i = 0;i<size;i++){
        List<Integer> copy = copy(ans.get(i), n);
        ans.add(copy);
    }
}

  • 来分析一下这个问题的时间复杂度，计算递归算法的时间复杂度方法是，找到递归的深度然后乘以每次递归中的迭代的次数，对于这个问题而言，递归的问题是N，但是我们发现每次递归for循环的迭代次数取决于res的长度，这并不是固定的

  • 依照刚才的思路，res的长度应该是每次递归都会翻倍，所以说总的迭代次数应该是2^N，这是因为一个大小为N的集合的自己总共会有2^N个，所以说res添加元素只有会有2^N，同时我们copy的时候，是把ans[i]复制一份添加到数组的最后，所以一次操作的时间是O(N)，还是比较耗时的

  • 回溯算法解决该问题

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

  • 如果涉及到路径和选择，那么得要想办法将该问题中有限的所有可能都给列举出来，如何将所有自己都穷举出来呢?

  • 我们手工分析一波

    • 首先base-case,空集[]是一个子集
    • 然后我们找以1开头的子集,[1]、[1,2]、[1,2,3]
    • 以2开头的子集,[2],[2,3]
    • 以3开头的子集,[3]

  • 最终以上这些自己加起来就是[1,2,3]的所有子集

  • 核心思路:用一个start参数控制递归，生成这样的一棵树，其实只要改造回溯算法的模板就可以了

private List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> subsets(int[] nums) {
    List<Integer> track = new ArrayList<>();
    backtrack(track,0,nums);
    return ans;
}
//backtrack(路径,选择列表)
private void backtrack(List<Integer> list,int start,int[] nums){
    //前序遍历的位置
    ans.add(copy(list));
    //从start开始,避免产生重复的子集
    for(int i = start;i<nums.length;i++){
        //做选择
        list.add(nums[i]);
        //递归回溯
        backtrack(list,i+1,nums);
        //撤销选择
        list.remove(list.size()-1);
    }
}
private List<Integer> copy(List<Integer> raw){
    List<Integer> newList = new ArrayList<>(raw);
    return newList;
}

4.1.2 组合

  • 输入两个数字n,k，算法输出[1...n]中k个数字的所有组合

  • 手工分析样例combine(4,2)

    • 以1开头的，长度为2的组合[1,2],[1,3],[1,4]

    • 以2开头的:[2,3],[2,4]

    • 以3开头的[3,4]

  • 这也是典型的回溯算法，k限制了树的高度，n限制了树的宽度

  • 套用回溯算法模板，其实我们可以发现，这其实就是一种特殊的子集，只不过这个子集的长度被限制了，限制了只有k

private List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> combine(int n, int k) {
    if(k<=0 || n<=0){
        return ans;
    }
    List<Integer> track = new ArrayList<>();
    backtrack(track,1,n,k);
    return ans;
}

private void backtrack(List<Integer> track,int start,int n,int k){
    if(track.size() == k){
        ans.add(new ArrayList<>(track));//copy简洁写法
        return;
    }
    for(int i = start;i<=n;i++){
        //做选择
        track.add(i);
        //递归回溯
        backtrack(track,i+1,n,k);
        //撤销选择
        track.remove(track.size()-1);
    }
}

4.1.3 排列

  • 输入一个不包含重复数字的数组nums，返回这些数字的全排列
  • 通过上面两个问题的理解，排列这个集合，是所有子集的子集，但是不同于组合，组合没有顺序要求(意思是就算不同顺序，它也算一个)，但是排列的话就是有顺序要求的，不同顺序也算一个
  • 那么如果要回溯的话，就需要手动来剔除那些不符合的排列
private List<List<Integer>> ans = new ArrayList<List<Integer>>();

public List<List<Integer>> permute(int[] nums) {
    List<Integer> track = new ArrayList<>();
    backtrack(track,nums);
    return ans;
}

//(路径,选择列表)
private void backtrack(List<Integer> track,int[] nums){
    //到达叶子节点
    if(track.size() == nums.length){
        ans.add(new ArrayList<>(track));
    }
    //做选择
    for(int i = 0;i<nums.length;i++){
        if(track.contains(nums[i])){
            continue;
        }
        //做选择
        track.add(nums[i]);
        //回溯递归
        backtrack(track,nums);
        //撤销选择
        track.remove(track.size()-1);
    }
}

4.2 回溯算法最佳实践:解数独

  • 对于解数独而言，我们的手工实践也许是穷举:算法对每一个空着的格子穷举1到9，如果遇到不合法的数字(在同一行或者同一列或同一个3*3的区域中存在相同的数字)则跳过，如果找到一个合法的数字，则继续穷举下一个空格子就好了
  • 输入是一个9*9的棋盘，其中有一些各自已经预先填入了数字，空白格子用点号字符.来表示，算法需要在原地修改棋盘，将空白格子填上数字，得到一个可行解

4.2.1 代码实现

  • 根据前文的回溯算法，求解数独的思路很直接，就是对每一个格子的所有可能的数字进行穷举，对于每个位置，有1-9这些数字的旋转，这就是选择列表，路径就是棋盘上的数字分布情况(也就是状态)

  • 基本代码框架

private void backtrack(char[][] board,int i,int j){
    int m =9,n=9;
    if(j==n){
        //如果穷举到最后一列的话就换行就好了
        backtrack(board,i+1,0);
        return;
    }
    //如果该位置是预设的数字,则不需要我们去推导
    if(board[i][j]!='.'){
        backtrack(board,i,j+1);
        return;
    }
    for(char ch = '1';ch<='9';ch++){
        //判定该数字是否合法
        if(!isValid(board,i,j,ch)){
            continue;
        }
        //做选择
        board[i][j] = ch;
        //继续穷举下一个位置
        backtrack(board,i,j+1);
        //撤销选择
        board[i][j] = '.';
    }
}
private boolean isValid(char[][] board,int row,int col,char ch){
    for(int i =0;i<9;i++){
        //判断行是否存在重复
        if(board[row][i] == ch){
            return false;
        }
        //判断列是否存在重复
        if(board[i][col] == ch){
            return false;
        }
        //判断3*3之内是否存在重复
        if(board[(row/3)*3+i/3][(col/3)*3+i%3] == ch){
            return false;
        }
    }
    return true;
}
  • 这个框架还缺少个递归结束条件，当r==m的时候就说明穷举完了最后一行，完成了所有的穷举，这就是base-case
  • 为了减少复杂度，可以让backtrack的函数返回值为boolean，如果找到了一个可行解，就返回true,这样可以组织后续的递归
public void solveSudoku(char[][] board) {
    backtrack(board,0,0);
}

private boolean backtrack(char[][] board,int i,int j){
    int m =9,n=9;
    if(i==m){
        //如果找到一个可行解,那么就触发base-case
        return true;
    }
    if(j==n){
        //如果穷举到最后一列的话就换行就好了
        return backtrack(board,i+1,0);
    }
    //如果该位置是预设的数字,则不需要我们去推导
    if(board[i][j]!='.'){
        return backtrack(board,i,j+1);
    }
    for(char ch = '1';ch<='9';ch++){
        //判定该数字是否合法
        if(!isValid(board,i,j,ch)){
            continue;
        }
        //做选择
        board[i][j] = ch;
        //继续穷举下一个位置
        if(backtrack(board,i,j+1)){
            return true;
        }
        //撤销选择
        board[i][j] = '.';
    }
    return false;
}
private boolean isValid(char[][] board,int row,int col,char ch){
    for(int i =0;i<9;i++){
        //判断行是否存在重复
        if(board[row][i] == ch){
            return false;
        }
        //判断列是否存在重复
        if(board[i][col] == ch){
            return false;
        }
        //判断3*3之内是否存在重复
        if(board[(row/3)*3+i/3][(col/3)*3+i%3] == ch){
            return false;
        }
    }
    return true;
}

4.3 回溯算法最佳实践:括号生成

  • 请你写一个算法，输入是一个正整数n，输出n对括号的所有合法组合

  • 合法括号的性质

    • 一个合法括号组合的左括号数量一定等于右括号数量
    • 对于一个合法的括号字符串组合p，必然对于任何0<=i<len(p)都有:子串p[0....i]中左括号的数量都大于等于右括号的数量

  • 以回溯的角度来说，可以转换为如下问题，现在有2n个位置，每个位置可以放置字符(或者)，组成的所有括号组合中，有多少个是符合的?最直观的想法就是从全部2^(2n)种组合中，根据上面总结出来的合法括号组合的性质选出合法的组合

  • 2^(2n)计算方法，每个位置有两个选择，一共有2n个位置，那就2n个2相乘，总情况数是2^(2n)

List<String> ans = new ArrayList<String>();
public List<String> generateParenthesis(int n) {
    if(n==0){
        return ans;
    }
    StringBuilder track = new StringBuilder();
    backtrack(track,n,n);
    return ans;
}

//路径,选择列表,i是当前的位置,n是规定的括号列表长度
private void backtrack(StringBuilder track,int left,int right){//可用的左括号数量为left个,可用的右括号数量为right个
    if(left<0 || right<0){
        return;
    }
    //如果左括号用得少,那么肯定不合法
    if(left>right){
        return;
    }
    //当所有括号都刚好用完的时候,那么就得到一个合法的组合了
    if(left ==0 && right ==0){
        ans.add(track.toString());
        return;
    }
    char[] choices= new char[]{'(',')'};
    for(int j = 0;j<choices.length;j++){
        //做选择
        track.append(choices[j]);
        //穷举下一个位置
        if(j== 0){
            backtrack(track,left-1,right);
        }
        if(j==1){
            backtrack(track,left,right-1);
        }
        //撤销选择
        track.deleteCharAt(track.length()-1);
    }
}

4.4 BFS算法暴力破解各种智力题(滑动谜题)

4.4.1 题目解析

  • 给你一个2*3的滑动拼图，用一个2X3的数组board来表示，拼图中有数字0-5,其中数字0就表示那个空着的格子，你可以通过移动其中的数字，当board变成[[1,2,3],[4,5,0]]的时候，赢得游戏，请你编写一个算法，计算赢得游戏所需要的最少移动次数，如果不能赢得游戏，请返回-1

4.4.2 思路分析

对于计算最小步数的问题，我们要敏感地想到搜索算法

  • 一般的BFS问题，是从一个起点start开始，向终点target进行寻路，但是拼图问题不是在寻路，而是在不断地交换数字
  • 这个问题假如能够转换为BFS问题，那么如何处理起点start和终点target呢?
  • 首先回答第一个问题，BFS算法并不只是一个寻路算法，而是一种暴力搜索算法，只要涉及到暴力穷举的问题，BFS就可以用，而且可以更快地找到答案
  • 那么问题就演化成了如何穷举出board当前局面下可能衍生出的所有局面
  • 这样其实就是一个BFS问题，每次先找到数字0，如何和周围的数字进行交换，形成新的局面后加入队列，当第一次到达target的时候，就到了赢得游戏的最少步数
  • 对于第二个问题，这里的board仅仅只是一个2X3的二维数组，所以可以压缩成一个一维字符串，其中比较有技巧性的点在于，二维数组有上下左右的概念，压缩成一维后，如何得到某一个索引上下左右的索引?
  • 这里给的一个方案是手写出一个映射表
vector<vector<int>> neighbor={
    {1,3},
    {0,4,2},
    {1,5},
    {0,4},
    {3,1,5}
    {4,5}
}
  • 其含义就是，在一维字符串中，索引i在二维数组中的相邻索引为neighbor[i]，注意这个顺序从上到下，从左到右的
public int slidingPuzzle(int[][] board) {
    //1.制作映射表
    int[][] neighbor = new int[6][];
    neighbor[0] = new int[]{1,3};
    neighbor[1] = new int[]{0,2,4};
    neighbor[2] = new int[]{1,5};
    neighbor[3] = new int[]{0,4};
    neighbor[4] = new int[]{1,3,5};
    neighbor[5] = new int[]{2,4};
    int m =2,n=3;
    StringBuilder start = new StringBuilder();
    StringBuilder target = new StringBuilder("123450");
    //将2X3的数组转化为字符串
    for(int i = 0;i<m;i++){
        for(int j =0;j<n;j++){
            start.append(board[i][j]);
        }
    }
    /*BFS搜索*/
    Queue<String> q = new LinkedList<>();
    Set<String> visited = new HashSet<>();
    q.offer(start.toString());
    visited.add(start.toString());
    int step = 0;
    while(!q.isEmpty()){
        int sz = q.size();
        for(int i =0;i<sz;i++){
            String head = q.poll();
            if(head.equals(target.toString())){
                return step;
            }
            //找到数字索引0
            int idx = 0;
            for(;head.toString().charAt(idx)!='0';idx++);
            //将数字0和响铃的数字交换位置
            for(int adj:neighbor[idx]){
                StringBuilder newBoard = new StringBuilder(head);
                char ch = newBoard.charAt(adj);
                newBoard.setCharAt(adj,newBoard.charAt(idx));
                newBoard.setCharAt(idx,ch);
                //防止走回头路
                if(!visited.contains(newBoard.toString())){
                    q.offer(newBoard.toString());
                    visited.add(newBoard.toString());
                }
            }
        }
        step++;
    }
    return -1;
}
文章作者: 穿山甲
文章链接: https://lumxi.github.io/2022/09/09/algorithm/labuladong/4.1-4.4note/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 穿山甲 !
Java leetcode
赏
  目录