搞懂回溯算法思想（LeetCode46、47、980）

我不是女神ヾ 2021-09-21 06:50 297阅读 0赞

### 一、回溯介绍 ###

**1.定义**

*  搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。
 *  它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。
 *  如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进,如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。

从上面的定义可以看出，回溯是跟DFS很相近的。

**2.公式伪代码**

void search(int k){ 
    
    	if (到目的地) 输出结果
    
        for(int i=1;i<=算符种类;i++){ 
            if(符合条件){ 
                保存条件
                search(k + 1);
                回溯，把保存的结果回退
            }
        }
        
    }
    
    PS:公式也不是万能的，不同的题目需要对公式进行不同的改进

--------------------

### 二、LeetCode例题 ###

力扣上面有很多回溯的题目，这里就简单举几个例子。

**（一）一维数组的全排列：LeetCode46. 全排列**

**【题目】**

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

**【示例】**

输入: [1,2,3]
    输出:
    [
      [1,2,3],
      [1,3,2],
      [2,1,3],
      [2,3,1],
      [3,1,2],
      [3,2,1]
    ]

**【代码】**

List<Integer> path;
        List<List<Integer>> paths;
        public List<List<Integer>> permute(int[] nums) { 
            path = new ArrayList<>();
            paths = new ArrayList<>();
            boolean[] flag = new boolean[nums.length];
            search(nums,flag);
    
            return paths;
        }
    
        public void search(int[] nums, boolean[] flag) { 
            if (path.size()==nums.length) { 
                paths.add(new ArrayList<>(path));
                return;
            }
            for(int i=0; i<nums.length; i++) { 
                if (!flag[i]) { 
                    flag[i] = true;
                    path.add(nums[i]);
                    search(nums, flag);
                    path.remove(path.size()-1);
                    flag[i] = false;
                }
            }
        }

**【思考】**

这个题目是非常典型的回溯，直接套公式就可以。**唯一需要注意的是在符合条件的时候，把path加入paths中的时候，需要创建一个副本对象加入**。

paths.add(new ArrayList<>(path));

如果不重新创建新的path，你们加入的结果在后面的回溯中还会被remove等操作，因为path的引用是同一个，执行的操作对象一直未变，所以需要创建新的对象。

--------------------

**（二）一维数组全排列+剪枝：LeetCode47. 全排列 II**

**【题目】**

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

**【示例】**

输入: [1,1,2]
    输出:
    [
      [1,1,2],
      [1,2,1],
      [2,1,1]
    ]

**【代码】**

List<Integer> path;
        List<List<Integer>> paths;
        public List<List<Integer>> permuteUnique(int[] nums) { 
            path = new ArrayList<>();
            paths = new ArrayList<>();
            Arrays.sort(nums);
            boolean[] flag = new boolean[nums.length];
            search(nums,flag);
    
            return paths;
        }
    
        public void search(int[] nums, boolean[] flag) { 
            if (path.size()==nums.length) { 
                paths.add(new ArrayList<>(path));
                return;
            }
            for(int i=0; i<nums.length; i++) { 
                if(i>0 && nums[i] == nums[i-1] && !flag[i-1]) continue;
                if (!flag[i]) { 
                    flag[i] = true;
                    path.add(nums[i]);
                    search(nums, flag);
                    path.remove(path.size()-1);
                    flag[i] = false;
                }
            }
        }

**【思考】**

基本的思路没有变，还是套回溯的公式，但是得到的结果会包含重复的排列，所以需要进行处理，要么对结果进行去重，要么在回溯的过程进行剪枝；对结果进行去重的操作大部分时候是超时的，因为本身回溯就是一种比较费时的操作，在回溯结束之后在去重操作，会额外增加时间复杂度。而剪枝正好相反，不仅不会增加时间复杂度还会减少时间复杂度。

**剪枝：在回溯过程把某些不合适的情况直接排除掉，不进入回溯的递归中。**

在这道题目中：先需要对数组进行排序，因为这样可以把相同的元素放在一起，**然后在算子的循环中加上相同的判断，相同的时候，就不进入回溯递归中。**

Arrays.sort(nums);// 排序
    
    // 其他操作
    
    if(i>0 && nums[i] == nums[i-1] && !flag[i-1]) continue; // 剪枝操作
    // 剪枝条件：i > 0 是为了保证 nums[i - 1] 有意义
    // 写 !flag[i - 1] 是因为要保证 nums[i - 1] 在深度优先遍历的过程中已经被加入path中，当nums[i]==nums[i-1]的时候，无论nums[i]是否
    // 能加入path，都要continue

--------------------

**（三）二维数组的路径选择：LeetCode980. 不同路径 III**

**【题目】**

在二维网格 grid 上，有 4 种类型的方格：

1 表示起始方格。且只有一个起始方格。  
2 表示结束方格，且只有一个结束方格。  
0 表示我们可以走过的空方格。  
\-1 表示我们无法跨越的障碍。

返回在四个方向（上、下、左、右）上行走时，**从起始方格到结束方格的不同路径的数目**，每一个无障碍方格都要通过一次。

PS：题目要求可能有很多种，比如：最长路径，最短时间，路径个数；万变不离其宗！

**【示例】**

输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
    输出：2
    解释：我们有以下两条路径：
    1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
    2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
    
    
    PS：注意看清题目，这是要求把所有的无障碍都走一遍的路径，而不是求任意路径

**【代码】**

int count;
        int[][] pos = { { 1,0},{ -1,0},{ 0,1},{ 0,-1}};
        public int uniquePathsIII(int[][] grid) { 
            if (grid==null || grid.length==0 || grid[0].length==0)
                return 0;
    
            int i,j,m,n,ans,s1,s2,e1,e2;
            m = grid.length;
            n = grid[0].length;
    
            ans = 0;
            s1 = s2 = e1 = e2 = 0;
            // 找到起点和终点的坐标以及无障碍通道的个数
            for (i=0; i<m; i++) { 
                for (j=0; j<n; j++) { 
                    if (grid[i][j]==1) { 
                        s1 = i;
                        s2 = j;
                    }
                    if (grid[i][j]==0)
                        ans++;
                }
            }
            
            boolean[][] flag = new boolean[m][n];
            flag[s1][s2] = true;
            count = 0;
            // 以起点为中心，上下左右递归回溯
            dfs(grid,flag,s1+1,s2,0,ans);
            dfs(grid,flag,s1-1,s2,0,ans);
            dfs(grid,flag,s1,s2+1,0,ans);
            dfs(grid,flag,s1,s2-1,0,ans);
    
            return count;
        }
    
        public void dfs(int[][] grid, boolean[][] flag,
                        int cur1, int cur2,
                        int curK, int ans) { 
            if (cur1<grid.length && cur2<grid[0].length && cur1>=0 && cur2>=0) { 
            	// 达到终点并且走的无障碍个数为全部个数
                if (grid[cur1][cur2]==2 && curK==ans) { 
                    count++;
                    return;
                }
                // 算子就是上下左右四个方向
                for (int i=0; i<4; i++) { 
                    if (!flag[cur1][cur2] && grid[cur1][cur2]==0) { 
                        flag[cur1][cur2] = true;
                        dfs(grid,flag,
                                cur1+pos[i][0],cur2+pos[i][1],
                                curK+1,ans);
                        flag[cur1][cur2] = false;
                    }
                }
            }
        }

**【思考】**

整体思路还是很明了的，基本上都是套公式，剪枝都在判断条件中体现出来，二维数组还需要注意边界越界的判断。

--------------------

**【Java 面试那点事】**

**这里致力于分享 Java 面试路上的各种知识，无论是技术还是经验，你需要的这里都有！**

**这里可以让你【快速了解 Java 相关知识】，并且【短时间在面试方面有跨越式提升】**

**面试路上，你不孤单！**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70]: /images/20210920/69efdb4c93b04b0f947b296290057473.png