回溯专题复习

谁践踏了优雅 2023-05-31 02:33 5阅读 0赞

# 回溯专题复习 #

> 最近在复习算法，为明年的春招做准备，欢迎互关呀，共同学习，进步！

## 1.全排列 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70]

### 过程分析 ###

> 递归树

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 1]

从递归树中可以看出，题目也要求数字不能重复，所以我们使用一个变量来标识一个数字是否被使用过。如果使用过则跳过使用下一个数字，使用完一个数字后要开始回溯，将访问状态重置

> 自己做题时的分析图，有点丑，自小写字比较难看hhh

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 2]

### 代码实现 ###

/**
         * @param nums
         * @return
         */
        public List<List<Integer>> permute(int[] nums) {
        
    
            List<List<Integer>> res = new ArrayList<>();
            int[] visited = new int[nums.length];
            backtrack(res, nums, new ArrayList<Integer>(), visited);
            return res;
    
        }
    
        /**
         * 递归回溯
         *
         * @param res   最终结果
         * @param nums
         * @param tmp   保存一次递归的结果
         * @param visited   一个排列中，数不能重复
         */
        private void backtrack(List<List<Integer>> res, int[] nums, ArrayList<Integer> tmp, int[] visited) {
        
            //每当找到一个合适的结果集就保存结果
            if (tmp.size() == nums.length) {
        
                //保存一次结果
                res.add(new ArrayList<>(tmp));
                return;
            }
            for (int i = 0; i < nums.length; i++) {
        
                //判断当前数是否被使用
                if (visited[i] == 1) {
        
                    continue;
                }
                //对使用过的数字标识 1
                visited[i] = 1;
                tmp.add(nums[i]);
                //使用下一个数字
                backtrack(res, nums, tmp, visited);
                //回溯，状态重置
                visited[i] = 0;
                tmp.remove(tmp.size() - 1);
            }
        }

## 2.全排列II ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 3]

### 过程分析 ###

这道题目其实和上一道差不多，只是要对上一道的结果集做一个去重

> 递归树

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 4]

### 代码实现 ###

class Solution {
        
        public List<List<Integer>> permuteUnique(int[] nums) {
        
            List<List<Integer>> res = new ArrayList<>();
            int[] visited = new int[nums.length];
            backtrack(res, nums, new ArrayList<Integer>(), visited);
            Set set = new HashSet(res);
            return new ArrayList<>(set);
        }
        
        /**
         * 递归回溯
         *
         * @param res   最终结果
         * @param nums
         * @param tmp   保存一次递归的结果
         * @param visited   一个排列中，数不能重复
         */
        private void backtrack(List<List<Integer>> res, int[] nums, ArrayList<Integer> tmp, int[] visited) {
        
            //每当找到一个合适的结果集就保存结果
            if (tmp.size() == nums.length) {
        
                //保存一次结果
                res.add(new ArrayList<>(tmp));
                return;
            }
            for (int i = 0; i < nums.length; i++) {
        
                //判断当前数是否被使用
                if (visited[i] == 1) {
        
                    continue;
                }
                //对使用过的数字标识 1
                visited[i] = 1;
                tmp.add(nums[i]);
                //使用下一个数字
                backtrack(res, nums, tmp, visited);
                //回溯，状态重置
                visited[i] = 0;
                tmp.remove(tmp.size() - 1);
            }
        }
    }

但是，这样实现，效率是有点低的，这就需要引出我们在回溯中的一个优化概念，剪枝

### 剪枝 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 5]

> 当数组中有重复元素的时候，可以先将数组排序，排序以后在递归的过程中可以很容易发现重复的元素。当发现重复元素的时候，让这一个分支跳过，以达到“剪枝”的效果，重复的排列就不会出现在结果集中

//保存结果集
        private List<List<Integer>> res = new ArrayList<>();
        //用于判断数字是否被使用过
        private boolean[] used;
    
        private void findPermuteUnique(int[] nums, int depth, Stack<Integer> stack) {
        
            if (depth == nums.length) {
        
                //符合结果集要求，保存一次结果
                res.add(new ArrayList<>(stack));
                return;
            }
            for (int i = 0; i < nums.length; i++) {
        
                if (!used[i]) {
        
                    //剪枝
                    if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
        
                        continue;
                    }
                    used[i] = true;
                    stack.add(nums[i]);
                    findPermuteUnique(nums, depth + 1, stack);
                    stack.pop();
                    used[i] = false;
                }
            }
        }
    
        public List<List<Integer>> permuteUnique(int[] nums) {
        
            int len = nums.length;
            if (len == 0) {
        
                return res;
            }
            Arrays.sort(nums);
            used = new boolean[len];
            findPermuteUnique(nums, 0, new Stack<>());
            return res;
        }

## 3.组合 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 6]

### 过程分析 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 7]

### 代码实现 ###

> 这样其实也是效率很低，有很多树枝是没必要走下去的

比如：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 8]

其中绿色的部分，是不能产生结果的分支，但是我们的代码确实又执行到了这部分

### 剪枝 ###

注意原来的

for(int i = start;i <= n;i++)

是在\[i，n\]这个闭区间中找到 k - tmp.size() 个元素。

但是并不是i <= n每一次都要走完，i有一个上限

> 比如，上图中的从5个数里边选出3个数这个递归树中所看到的

当递归树取3后，只能走到\[4,5\]，之后取5，取完5之后发现能取的数的集合是一个空集，但是如果是\[i，n\]这个区间的话，代码还是走了这多余的一步。所以，我们剪枝的目的就是为了能让代码及时在走多余的一步前，退出循环

> 现在假设，k = 6，n = 4

*      tmp.size() == 1 的时候，接下来要选择 3 个元素， i 最大的值是 4，最后一个被选的是 [4,5,6]；
 *      tmp.size() == 2 的时候，接下来要选择 2 个元素， i 最大的值是 5，最后一个被选的是 [5,6]；
 *      tmp.size() == 3 的时候，接下来要选择 1 个元素， i 最大的值是 6，最后一个被选的是 [6]；

所以，剪枝过程就是：把 i <= n 改成 i <= n - (k - pre.size()) + 1

private List<List<Integer>> res = new ArrayList<>();
        public List<List<Integer>> combine(int n, int k) {
        
            if (n <= 0 || k <= 0 || n < k) {
        
                return res;
            }
            generateCombinations(n,k,1,new Stack());
            return res;
        }
    
        private void generateCombinations(int n, int k, int start, Stack tmp){
        
            if(tmp.size() == k){
        
                res.add(new ArrayList<>(tmp));
                return;
            }
            //for(int i = start;i <= n;i++){
        
            //剪枝
            for(int i = start;i <=n - (k - tmp.size()) + 1;i++){
        
                /**
                 * 从 [i, n] 这个区间里（注意，左右都是闭区间），找到 k - tmp.size() 个元素。
                 * i <= n 不是每一次都要走完的， i 有一个上限。
                 *
                 * 再如：如果 n = 6 ，k = 4，
                 * tmp.size() == 1 的时候，接下来要选择 3 个元素， i 最大的值是 4，最后一个被选的是 [4,5,6]；
                 * tmp.size() == 2 的时候，接下来要选择 2 个元素， i 最大的值是 5，最后一个被选的是 [5,6]；
                 * tmp.size() == 3 的时候，接下来要选择 1 个元素， i 最大的值是 6，最后一个被选的是 [6]；
                 *
                 * 所以，剪枝过程就是：把 i <= n 改成 i <= n - (k - pre.size()) + 1
                 */
                tmp.add(i);
                generateCombinations(n, k, i + 1, tmp);
                tmp.pop();
            }
        }

## 4.组合总和 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 9]

### 过程分析 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 10]

### 代码实现 ###

private List<List<Integer>> res = new ArrayList<>();
    
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
        
            //先排序
            Arrays.sort(candidates);
            combinationSum(candidates,0, target,new ArrayList<Integer>());
            return res;
        }   
    
        private void combinationSum(int[] candidates,int index, int target, ArrayList<Integer> tmp) {
        
            if(target == 0){
        
                //Java中可变对象是引用传递，因此需要将当前 path 里的值拷贝出来
                res.add(new ArrayList<>(tmp));
                return;
            }
            //确保目标数小于所取数
            for(int i = index;i < candidates.length && target - candidates[i] >= 0;i++){
        
                tmp.add(candidates[i]);
                combinationSum(candidates, i, target - candidates[i], tmp);
                tmp.remove(tmp.size() - 1);
            }
        }

> 其实以上代码是已经做了剪枝处理的了

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 11]

所以剪枝处理就是将nums数组先做一个排序，然后保证每次取的数都小于或等于目标数

Arrays.sort(candidates);
    
    i < candidates.length && target - candidates[i] >= 0

## 5.组合总和II ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 12]

### 过程分析 ###

这道题目跟原来组合总和一的区别就是在这道题目中，数字只可以取一次，那么我们就用一个数组来标识一下使用状态，每次回溯的时候在将状态重置

### 代码实现 ###

private List<List<Integer>> res = new ArrayList<>();
        //判断是否使用过
        private boolean[] b;
    
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        
            b = new boolean[candidates.length];
            Arrays.sort(candidates);
            combinationSum(candidates,0, target,new ArrayList<Integer>());
            //结果集去重
            Set set = new HashSet(res);
            return new ArrayList<>(set);
        }
    
        private void combinationSum(int[] candidates,int index, int target, ArrayList<Integer> tmp) {
        
            if(target == 0){
        
                //Java中可变对象是引用传递，因此需要将当前 path 里的值拷贝出来
                res.add(new ArrayList<>(tmp));
                return;
            }
            for(int i = index;i < candidates.length && target - candidates[i] >= 0;i++){
        
                if(b[i] == false){
        
                    b[i] = true;
                    tmp.add(candidates[i]);
                    combinationSum(candidates, i + 1, target - candidates[i], tmp);
                    b[i] = false;
                    tmp.remove(tmp.size() - 1);
                }
            }
        }

### 剪枝 ###

if(i > index && candidates[i - 1] == candidates[i]){
        
                    //重复 i > index 的元素
                    continue;
                }

## 6.组合总和III ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 13]

### 过程分析 ###

这个问题可以看成是从1到9这些数中选出k个相加为n的数，且这k个数不能重复，这样就跟之前的组合I和组合II相似了

### 代码实现 ###

private List<List<Integer>> ans = new ArrayList<>();
    
        public List<List<Integer>> combinationSum3(int k, int n) {
        
            traceBack(k, n, 0, 1, new LinkedList<>());
            return ans;
        }
    
        public void traceBack(int k, int n, int sum, int begin, LinkedList<Integer> list) {
        
            if(list.size() == k){
        
                if(n == sum){
        
                    ans.add(new ArrayList<>(list));
                }
                return;
            }
            for(int i = begin;i < 10;i++){
        
                list.add(i);
                traceBack(k,n,sum + i,i + 1,list);
                list.removeLast();
            }
        }

## 7.N皇后 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 14]

> N皇后是最为经典的回溯算法，是一个二维平面上的回溯算法，考虑的点要比一维平面要多

### 过程分析 ###

以4皇后画出递归树分析：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 15]

N皇后问题有几个限制：

*  同一行只能放一个
 *  同一列只能放一个
 *  同一条对角线只能放一个

对于这个二维的“棋盘”，其对角线可以这样标识：

*  dia1\[i\]:对角线i被占用 2\*n-1条对角线 左下到右上方向：x+y
 *  dia2\[i\]:对角线i被占用 2\*n-1条对角线 左上到右下方向：x-y+n-1

### 代码实现 ###

private boolean[] col;
        private boolean[] left;
        private boolean[] right;
        private List<List<String>> res = new ArrayList<>();
    	
        public List<List<String>> solveNQueens(int n) {
        
            col = new boolean[n];
            left = new boolean[2*n-1];
            right = new boolean[2*n-1];
            char[][] board = new char[n][n];
            putQueue(board, 0, n);
            return res;
        }
    
        /**
         * 尝试在一个n皇后问题中，摆放第index行的皇后位置
         * @param board
         * @param index
         * @param n
         */
        private void putQueue(char[][] board, int index, int n) {
        
            if (index >= n) {
        
                List<String> list = new ArrayList<>();
                for (int i = 0; i < n; i++) {
        
                    list.add(new String(board[i]));
                }
                res.add(list);
                return;
            }
            Arrays.fill(board[index], '.');
            for (int i = 0; i < n; i++) {
        
                if (!col[i] && !left[index + i] && !right[index - i + n - 1]) {
        
                    //列不冲突 && 对角线不冲突
                    board[index][i] = 'Q';
                    col[i] = true;
                    left[index + i] = true;
                    right[index - i + n - 1] = true;
                    //下一行
                    putQueue(board, index + 1, n);
                    //回溯，状态重置
                    board[index][i] = '.';
                    col[i] = false;
                    left[index + i] = false;
                    right[index - i + n - 1] = false;
                }
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70]: /images/20230531/41ff2b97a72c4cceaa3ed7efe24548ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 1]: /images/20230531/f6db7bfb3c14495c9ecbb63b2544b103.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 2]: /images/20230531/1c6848079bbe4a959c259461c58d59fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 3]: /images/20230531/1861b16824ea47c19c5619fe573fcd7b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 4]: /images/20230531/113739803b2744b6a20d10fa21c0af1e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 5]: /images/20230531/28a03863344f4e72a0553181078c025b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 6]: /images/20230531/49e013ef173f44f59c1ae81e77d1f37a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 7]: /images/20230531/f19006d7e1944c088783f59c9ecd74ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 8]: /images/20230531/c759671f16fd4de3860920c685cea5bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 9]: /images/20230531/d19149821be745298de525a5522442d2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 10]: /images/20230531/f267db3dee6142d0835f412acdf5abf9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 11]: /images/20230531/b7d5b86580374fe798ca901d36a7b7ec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 12]: /images/20230531/a660fdd2ecad4285ae4bf7845d96e84c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 13]: /images/20230531/fcb01e02c6744b6fa597d03266563e0a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 14]: /images/20230531/ebc5e07659334d8b9aa0ee80fefc1a65.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 15]: /images/20230531/8d3ea2dfc0c34350931d3c1282e1e850.png