面试算法大全-回溯算法总结

偏执的太偏执、 2022-10-17 13:51 212阅读 0赞

## 9、回溯 ##

### 9.1 回溯算法总结（DFS） ###

回溯算法和DFS一个样子

void backtracking(参数) {
        
        if (终止条件) {
        
            存放结果;
            return;
        }
        for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        
            处理节点;
            backtracking(路径，选择列表); // 递归
            回溯，撤销处理结果
        }
    }

代码方面，回溯算法的框架：

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

**其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」**，特别简单。

### 9.2 经典题目源码总结 ###

#### [八皇后][Link 1] ####

public void solveNQueens(int n) {
        
        char[][] chess = new char[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                chess[i][j] = '.';
        solve(chess, 0);
    }
    
    private void solve(char[][] chess, int row) {
        
        if (row == chess.length) {
        
            //自己写的一个公共方法，打印二维数组的，
            // 主要用于测试数据用的
            Util.printTwoCharArrays(chess);
            System.out.println();
            return;
        }
        for (int col = 0; col < chess.length; col++) {
        
            if (valid(chess, row, col)) {
        
                chess[row][col] = 'Q';
                solve(chess, row + 1);
                chess[row][col] = '.';
            }
        }
    }
    
    //row表示第几行，col表示第几列
    private boolean valid(char[][] chess, int row, int col) {
        
        //判断当前列有没有皇后,因为他是一行一行往下走的，
        //我们只需要检查走过的行数即可，通俗一点就是判断当前
        //坐标位置的上面有没有皇后
        for (int i = 0; i < row; i++) {
        
            if (chess[i][col] == 'Q') {
        
                return false;
            }
        }
        //判断当前坐标的右上角有没有皇后
        for (int i = row - 1, j = col + 1; i >= 0 && j < chess.length; i--, j++) {
        
            if (chess[i][j] == 'Q') {
        
                return false;
            }
        }
        //判断当前坐标的左上角有没有皇后
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        
            if (chess[i][j] == 'Q') {
        
                return false;
            }
        }
        return true;
    }

#### [N 皇后][N] ####

class Solution {
        
        public List<List<String>> solveNQueens(int n) {
        
            List<List<String>> result = new ArrayList<>();
            List<char[]> board = new ArrayList<>();
            for (int i = 0; i < n; i++) {
        
                char[] chars = new char[n];
                Arrays.fill(chars, '.');
                board.add(chars);
            }
            backtracking(n, 0, board, result);
            return result;
        }
        private void backtracking(int n, int row, List<char[]> board, List<List<String>> result) {
        
            if (n == row) {
        
                List<String> path = new ArrayList<>();
                for (char[] chars : board) {
        
                    path.add(new String(chars));
                }
                result.add(path);
                return;
            }
            for (int col = 0; col < n; col++) {
        
                if (isValid(row, col, n, board)) {
        
                    board.get(row)[col] = 'Q';
                    backtracking(n, row + 1, board, result);
                    board.get(row)[col] = '.';
                }
            }
        }
        private boolean isValid(int row, int col, int n, List<char[]> board) {
        
            for (int i = 0; i < row; i++) {
        
                if (board.get(i)[col] == 'Q') {
        
                    return false;
                }
            }
            for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        
                if (board.get(i)[j] == 'Q') {
        
                    return false;
                }
            }
            for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        
                if (board.get(i)[j] == 'Q') {
        
                    return false;
                }
            }
            return true;
        }
    }

public List<List<String>> solveNQueens(int n) {
        
            char[][] chess = new char[n][n];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    chess[i][j] = '.';
            List<List<String>> res = new ArrayList<>();
            solve(res, chess, 0);
            return res;
        }
    
        private void solve(List<List<String>> res, char[][] chess, int row) {
        
            if (row == chess.length) {
        
                res.add(construct(chess));
                return;
            }
            for (int col = 0; col < chess.length; col++) {
        
                if (valid(chess, row, col)) {
        
                    chess[row][col] = 'Q';
                    solve(res, chess, row + 1);
                    chess[row][col] = '.';
                }
            }
        }
    
        //row表示第几行，col表示第几列
        private boolean valid(char[][] chess, int row, int col) {
        
            //判断当前列有没有皇后,因为他是一行一行往下走的，
            //我们只需要检查走过的行数即可，通俗一点就是判断当前
            //坐标位置的上面有没有皇后
            for (int i = 0; i < row; i++) {
        
                if (chess[i][col] == 'Q') {
        
                    return false;
                }
            }
            //判断当前坐标的右上角有没有皇后
            for (int i = row - 1, j = col + 1; i >= 0 && j < chess.length; i--, j++) {
        
                if (chess[i][j] == 'Q') {
        
                    return false;
                }
            }
            //判断当前坐标的左上角有没有皇后
            for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        
                if (chess[i][j] == 'Q') {
        
                    return false;
                }
            }
            return true;
        }
    
        //把数组转为list
        private List<String> construct(char[][] chess) {
        
            List<String> path = new ArrayList<>();
            for (int i = 0; i < chess.length; i++) {
        
                path.add(new String(chess[i]));
            }
            return path;
        }

#### [N皇后 II][N_ II] ####

class Solution {
        
        public int totalNQueens(int n) {
        
            Set<Integer> columns = new HashSet<Integer>();
            Set<Integer> diagonals1 = new HashSet<Integer>();
            Set<Integer> diagonals2 = new HashSet<Integer>();
            return backtrack(n, 0, columns, diagonals1, diagonals2);
        }
    
        public int backtrack(int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
        
            if (row == n) {
        
                return 1;
            } else {
        
                int count = 0;
                for (int i = 0; i < n; i++) {
        
                    if (columns.contains(i)) {
        
                        continue;
                    }
                    int diagonal1 = row - i;
                    if (diagonals1.contains(diagonal1)) {
        
                        continue;
                    }
                    int diagonal2 = row + i;
                    if (diagonals2.contains(diagonal2)) {
        
                        continue;
                    }
                    columns.add(i);
                    diagonals1.add(diagonal1);
                    diagonals2.add(diagonal2);
                    count += backtrack(n, row + 1, columns, diagonals1, diagonals2);
                    columns.remove(i);
                    diagonals1.remove(diagonal1);
                    diagonals2.remove(diagonal2);
                }
                return count;
            }
        }
    }

#### [组合][Link 2] ####

方法一：根据搜索起点画出二叉树

![img][]

import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.Deque;
    import java.util.List;
    
    public class Solution {
        
    
        public List<List<Integer>> combine(int n, int k) {
        
            List<List<Integer>> res = new ArrayList<>();
            if (k <= 0 || n < k) {
        
                return res;
            }
            // 从 1 开始是题目的设定
            Deque<Integer> path = new ArrayDeque<>();
            dfs(n, k, 1, path, res);
            return res;
        }
    
        private void dfs(int n, int k, int begin, Deque<Integer> path, List<List<Integer>> res) {
        
            // 递归终止条件是：path 的长度等于 k
            if (path.size() == k) {
        
                res.add(new ArrayList<>(path));
                return;
            }
    
            // 遍历可能的搜索起点
            for (int i = begin; i <= n; i++) {
        
                // 向路径变量里添加一个数
                path.addLast(i);
                // 下一轮搜索，设置的搜索起点要加 1，因为组合数理不允许出现重复的元素
                dfs(n, k, i + 1, path, res);
                // 重点理解这里：深度优先遍历有回头的过程，因此递归之前做了什么，递归之后需要做相同操作的逆向操作
                path.removeLast();
            }
        }
    }

测试代码：

import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.Deque;
    import java.util.List;
    
    public class Solution {
        
    
        public List<List<Integer>> combine(int n, int k) {
        
            List<List<Integer>> res = new ArrayList<>();
            if (k <= 0 || n < k) {
        
                return res;
            }
            Deque<Integer> path = new ArrayDeque<>();
            dfs(n, k, 1, path, res);
            return res;
        }
    
        private void dfs(int n, int k, int begin, Deque<Integer> path, List<List<Integer>> res) {
        
            if (path.size() == k) {
        
                res.add(new ArrayList<>(path));
                return;
            }
            for (int i = begin; i <= n; i++) {
        
                path.addLast(i);
                System.out.println("递归之前 => " + path);
                dfs(n, k, i + 1, path, res);
                path.removeLast();
                System.out.println("递归之后 => " + path);
            }
        }
    
        public static void main(String[] args) {
        
            Solution solution = new Solution();
            int n = 5;
            int k = 3;
            List<List<Integer>> res = solution.combine(n, k);
            System.out.println(res);
        }
    }

优化：分析搜索起点的上界进行剪枝

![img][img 1]

import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.Deque;
    import java.util.List;
    
    public class Solution {
        
    
        public List<List<Integer>> combine(int n, int k) {
        
            List<List<Integer>> res = new ArrayList<>();
            if (k <= 0 || n < k) {
        
                return res;
            }
            Deque<Integer> path = new ArrayDeque<>();
            dfs(n, k, 1, path, res);
            return res;
        }
    
        private void dfs(int n, int k, int index, Deque<Integer> path, List<List<Integer>> res) {
        
            if (path.size() == k) {
        
                res.add(new ArrayList<>(path));
                return;
            }
    
            // 只有这里 i <= n - (k - path.size()) + 1 与参考代码 1 不同
            for (int i = index; i <= n - (k - path.size()) + 1; i++) {
        
                path.addLast(i);
                dfs(n, k, i + 1, path, res);
                path.removeLast();
            }
        }
    }

方法二：按照每一个数选与不选画出二叉树

![img][img 2]

import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.Deque;
    import java.util.List;
    
    public class Solution {
        
    
        public List<List<Integer>> combine(int n, int k) {
        
            List<List<Integer>> res = new ArrayList<>();
            if (k <= 0 || n < k) {
        
                return res;
            }
    
            // 为了防止底层动态数组扩容，初始化的时候传入最大长度
            Deque<Integer> path = new ArrayDeque<>(k);
            dfs(1, n, k, path, res);
            return res;
        }
    
        private void dfs(int begin, int n, int k, Deque<Integer> path, List<List<Integer>> res) {
        
            if (k == 0) {
        
                res.add(new ArrayList<>(path));
                return;
            }
    
            // 基础版本的递归终止条件：if (begin == n + 1) {
        
            if (begin > n - k + 1) {
        
                return;
            }
            // 不选当前考虑的数 begin，直接递归到下一层
            dfs(begin + 1, n, k, path, res);
    
            // 不选当前考虑的数 begin，递归到下一层的时候 k - 1，这里 k 表示还需要选多少个数
            path.addLast(begin);
            dfs(begin + 1, n, k - 1, path, res);
            // 深度优先遍历有回头的过程，因此需要撤销选择
            path.removeLast();
        }
    }

#### [组合总和][Link 3] ####

![img][img 3]

class Solution {
        
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
        
            List<List<Integer>> ans = new ArrayList<List<Integer>>();
            List<Integer> combine = new ArrayList<Integer>();
            dfs(candidates, target, ans, combine, 0);
            return ans;
        }
    
        public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
        
            if (idx == candidates.length) {
        
                return;
            }
            if (target == 0) {
        
                ans.add(new ArrayList<Integer>(combine));
                return;
            }
            // 直接跳过
            dfs(candidates, target, ans, combine, idx + 1);
            // 选择当前数
            if (target - candidates[idx] >= 0) {
        
                combine.add(candidates[idx]);
                dfs(candidates, target - candidates[idx], ans, combine, idx);
                combine.remove(combine.size() - 1);
            }
        }
    }

#### [ 组合总和 II][_ II] ####

方法一：递归

class Solution {
        
        List<int[]> freq = new ArrayList<int[]>();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> sequence = new ArrayList<Integer>();
    
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        
            Arrays.sort(candidates);
            for (int num : candidates) {
        
                int size = freq.size();
                if (freq.isEmpty() || num != freq.get(size - 1)[0]) {
        
                    freq.add(new int[]{
        num, 1});
                } else {
        
                    ++freq.get(size - 1)[1];
                }
            }
            dfs(0, target);
            return ans;
        }
    
        public void dfs(int pos, int rest) {
        
            if (rest == 0) {
        
                ans.add(new ArrayList<Integer>(sequence));
                return;
            }
            if (pos == freq.size() || rest < freq.get(pos)[0]) {
        
                return;
            }
    
            dfs(pos + 1, rest);
    
            int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);
            for (int i = 1; i <= most; ++i) {
        
                sequence.add(freq.get(pos)[0]);
                dfs(pos + 1, rest - i * freq.get(pos)[0]);
            }
            for (int i = 1; i <= most; ++i) {
        
                sequence.remove(sequence.size() - 1);
            }
        }
    }

方法二：回溯算法

![img][img 4]

![img][img 5]

import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Deque;
    import java.util.List;
    
    public class Solution {
        
    
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        
            int len = candidates.length;
            List<List<Integer>> res = new ArrayList<>();
            if (len == 0) {
        
                return res;
            }
    
            // 关键步骤
            Arrays.sort(candidates);
    
            Deque<Integer> path = new ArrayDeque<>(len);
            dfs(candidates, len, 0, target, path, res);
            return res;
        }
    
        /**
         * @param candidates 候选数组
         * @param len        冗余变量
         * @param begin      从候选数组的 begin 位置开始搜索
         * @param target     表示剩余，这个值一开始等于 target，基于题目中说明的"所有数字（包括目标数）都是正整数"这个条件
         * @param path       从根结点到叶子结点的路径
         * @param res
         */
        private void dfs(int[] candidates, int len, int begin, int target, Deque<Integer> path, List<List<Integer>> res) {
        
            if (target == 0) {
        
                res.add(new ArrayList<>(path));
                return;
            }
            for (int i = begin; i < len; i++) {
        
                // 大剪枝：减去 candidates[i] 小于 0，减去后面的 candidates[i + 1]、candidates[i + 2] 肯定也小于 0，因此用 break
                if (target - candidates[i] < 0) {
        
                    break;
                }
    
                // 小剪枝：同一层相同数值的结点，从第 2 个开始，候选数更少，结果一定发生重复，因此跳过，用 continue
                if (i > begin && candidates[i] == candidates[i - 1]) {
        
                    continue;
                }
    
                path.addLast(candidates[i]);
                // 调试语句 ①
                // System.out.println("递归之前 => " + path + "，剩余 = " + (target - candidates[i]));
    
                // 因为元素不可以重复使用，这里递归传递下去的是 i + 1 而不是 i
                dfs(candidates, len, i + 1, target - candidates[i], path, res);
    
                path.removeLast();
                // 调试语句 ②
                // System.out.println("递归之后 => " + path + "，剩余 = " + (target - candidates[i]));
            }
        }
    
        public static void main(String[] args) {
        
            int[] candidates = new int[]{
        10, 1, 2, 7, 6, 1, 5};
            int target = 8;
            Solution solution = new Solution();
            List<List<Integer>> res = solution.combinationSum2(candidates, target);
            System.out.println("输出 => " + res);
        }
    }

#### [组合总和 III][III] ####

方法一：组合枚举

class Solution {
        
        List<Integer> temp = new ArrayList<Integer>();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
    
        public List<List<Integer>> combinationSum3(int k, int n) {
        
            dfs(1, 9, k, n);
            return ans;
        }
    
        public void dfs(int cur, int n, int k, int sum) {
        
            if (temp.size() + (n - cur + 1) < k || temp.size() > k) {
        
                return;
            }
            if (temp.size() == k) {
        
                int tempSum = 0;
                for (int num : temp) {
        
                    tempSum += num;
                }
                if (tempSum == sum) {
        
                    ans.add(new ArrayList<Integer>(temp));
                    return;
                }
            }
            temp.add(cur);
            dfs(cur + 1, n, k, sum);
            temp.remove(temp.size() - 1);
            dfs(cur + 1, n, k, sum);
        }
    }

方法二：回溯 + 剪枝

![img][img 6]

import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.Deque;
    import java.util.List;
    
    public class Solution {
        
    
        public List<List<Integer>> combinationSum3(int k, int n) {
        
            List<List<Integer>> res = new ArrayList<>();
    
            // 一开始做一些特殊判断
            if (k <= 0 || n <= 0 || k > n) {
        
                return res;
            }
    
            // 寻找 n 的上限：[9, 8, ... , (9 - k + 1)]，它们的和为 (19 - k) * k / 2
            // 比上限还大，就不用搜索了：
            if (n > (19 - k) * k / 2) {
        
                return res;
            }
    
            // 根据官方对 Stack 的使用建议，这里将 Deque 对象当做 stack 使用
            // 注意只使用关于栈的接口
            Deque<Integer> path = new ArrayDeque<>();
            dfs(k, n, 1, path, res);
            return res;
        }
    
        /**
         * @param k       剩下要找 k 个数
         * @param residue 剩余多少
         * @param start   下一轮搜索的起始元素是多少
         * @param path    深度优先遍历的路径参数（状态变量）
         * @param res     保存结果集的列表
         */
        private void dfs(int k, int residue, int start, Deque<Integer> path, List<List<Integer>> res) {
        
            // 剪枝：[start, 9] 这个区间里的数都不够 k 个，不用继续往下搜索
            if (10 - start < k) {
        
                return;
            }
            if (k == 0) {
        
                if (residue == 0) {
        
                    res.add(new ArrayList<>(path));
                    return;
                }
            }
    
            // 枚举起点值 [..., 7, 8, 9]
            // 找 3 个数，起点最多到 7
            // 找 2 个数，起点最多到 8
            // 规律是，起点上界 + k = 10，故起点上界 = 10 - k
            for (int i = start; i <= 10 - k; i++) {
        
    
    //            if ((2 * i + k - 1) * k / 2 > residue) {
        
    //                break;
    //            }
    
                // 剪枝
                if (residue - i < 0) {
        
                    break;
                }
                path.addLast(i);
                dfs(k - 1, residue - i, i + 1, path, res);
                path.removeLast();
            }
        }
    }

方法三：回溯算法

public List<List<Integer>> combinationSum3(int k, int n) {
        
            List<List<Integer>> res = new ArrayList<>();
            dfs(res, new ArrayList<>(), k, 1, n);
            return res;
        }
    
        private void dfs(List<List<Integer>> res, List<Integer> list, int k, int start, int n) {
        
            //终止条件，如果满足这个条件，再往下找也没什么意义了
            if (list.size() == k || n <= 0) {
        
                //如果找到一组合适的就把他加入到集合list中
                if (list.size() == k && n == 0)
                    res.add(new ArrayList<>(list));
                return;
            }
            for (int i = start; i <= 9; i++) {
        
                //选择当前值
                list.add(i);
                //递归
                dfs(res, list, k, i + 1, n - i);
                //撤销选择
                list.remove(list.size() - 1);
            }
        }

方法四：递归解法

![img][img 7]

public List<List<Integer>> combinationSum3(int k, int n) {
        
            List<List<Integer>> res = new ArrayList<>();
            dfs(res, new ArrayList<>(), k, 1, n);
            return res;
        }
    
        private void dfs(List<List<Integer>> res, List<Integer> list, int k, int start, int n) {
        
            //终止条件，如果满足这个条件，再往下找也没什么意义了
            if (list.size() == k || n <= 0) {
        
                //如果找到一组合适的就把他加入到集合list中
                if (list.size() == k && n == 0)
                    res.add(new ArrayList<>(list));
                return;
            }
            for (int i = start; i <= 9; i++) {
        
                //创建一个新的list，和原来的list撇清关系，对当前list的修改并不会影响到之前的list
                List<Integer> subList = new LinkedList<>(list);
                subList.add(i);
                //递归
                dfs(res, subList, k, i + 1, n - i);
                //注意这里没有撤销的操作，因为是在一个新的list中的修改，原来的list并没有修改，所以不需要撤销操作
            }
        }

#### [全排列][Link 4] ####

方法一：搜索回溯

class Solution {
        
        public List<List<Integer>> permute(int[] nums) {
        
            List<List<Integer>> res = new ArrayList<List<Integer>>();
    
            List<Integer> output = new ArrayList<Integer>();
            for (int num : nums) {
        
                output.add(num);
            }
    
            int n = nums.length;
            backtrack(n, output, res, 0);
            return res;
        }
    
        public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
        
            // 所有数都填完了
            if (first == n) {
        
                res.add(new ArrayList<Integer>(output));
            }
            for (int i = first; i < n; i++) {
        
                // 动态维护数组
                Collections.swap(output, first, i);
                // 继续递归填下一个数
                backtrack(n, output, res, first + 1);
                // 撤销操作
                Collections.swap(output, first, i);
            }
        }
    }

方法二：回溯算法与深度优先遍历

![img][img 8]

import java.util.ArrayList;
    import java.util.List;
    
    
    public class Solution {
        
    
        public List<List<Integer>> permute(int[] nums) {
        
            int len = nums.length;
            // 使用一个动态数组保存所有可能的全排列
            List<List<Integer>> res = new ArrayList<>();
            if (len == 0) {
        
                return res;
            }
    
            boolean[] used = new boolean[len];
            List<Integer> path = new ArrayList<>();
    
            dfs(nums, len, 0, path, used, res);
            return res;
        }
    
        private void dfs(int[] nums, int len, int depth,
                         List<Integer> path, boolean[] used,
                         List<List<Integer>> res) {
        
            if (depth == len) {
        
                res.add(path);
                return;
            }
            // 在非叶子结点处，产生不同的分支，这一操作的语义是：在还未选择的数中依次选择一个元素作为下一个位置的元素，这显然得通过一个循环实现。
            for (int i = 0; i < len; i++) {
        
                if (!used[i]) {
        
                    path.add(nums[i]);
                    used[i] = true;
                    dfs(nums, len, depth + 1, path, used, res);
                    // 注意：下面这两行代码发生 「回溯」，回溯发生在从 深层结点 回到 浅层结点 的过程，代码在形式上和递归之前是对称的
                    used[i] = false;
                    path.remove(path.size() - 1);
                }
            }
        }
        public static void main(String[] args) {
        
            int[] nums = {
        1, 2, 3};
            Solution solution = new Solution();
            List<List<Integer>> lists = solution.permute(nums);
            System.out.println(lists);
        }
    }

#### [全排列 II][II] ####

方法一：回溯搜索 + 剪枝

![img][img 9]

方法二：搜索回溯

class Solution {
        
        boolean[] vis;
    
        public List<List<Integer>> permuteUnique(int[] nums) {
        
            List<List<Integer>> ans = new ArrayList<List<Integer>>();
            List<Integer> perm = new ArrayList<Integer>();
            vis = new boolean[nums.length];
            Arrays.sort(nums);
            backtrack(nums, ans, 0, perm);
            return ans;
        }
    
        public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
        
            if (idx == nums.length) {
        
                ans.add(new ArrayList<Integer>(perm));
                return;
            }
            for (int i = 0; i < nums.length; ++i) {
        
                if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
        
                    continue;
                }
                perm.add(nums[i]);
                vis[i] = true;
                backtrack(nums, ans, idx + 1, perm);
                vis[i] = false;
                perm.remove(idx);
            }
        }
    }

#### [黄金矿工][Link 5] ####

![img][img 10]

![img][img 11]

public int getMaximumGold(int[][] grid) {
        
            //边界条件判断
            if (grid == null || grid.length == 0)
                return 0;
            //保存最大路径值
            int res = 0;
            //两个for循环，遍历每一个位置，让他们当做起点
            //查找最大路径值
            for (int i = 0; i < grid.length; i++) {
        
                for (int j = 0; j < grid[0].length; j++) {
        
                    //函数dfs是以坐标(i,j)为起点，查找最大路径值
                    res = Math.max(res, dfs(grid, i, j));
                }
            }
            //返回最大路径值
            return res;
        }
    
        public int dfs(int[][] grid, int i, int j) {
        
            //边界条件的判断，x,y都不能越界，同时当前坐标的位置如果是0，表示有障碍物
            //或者遍历过了
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0)
            return 0;
            //先把当前坐标的值保存下来，最后再还原
            int temp = grid[i][j];
            //当前坐标已经访问过了，要把他标记为0，防止再次访问
            grid[i][j] = 0;
            //然后沿着当前坐标的上下左右4个方向查找
            int up = dfs(grid, i, j - 1);//往上找
            int down = dfs(grid, i, j + 1);//往下找
            int left = dfs(grid, i - 1, j);//往左找
            int right = dfs(grid, i + 1, j);//往右找
            //这里只要4个方向的最大值即可
            int max = Math.max(left, Math.max(right, Math.max(up, down)));
            //然后再把当前位置的值还原
            grid[i][j] = temp;
            //返回最大路径值
            return grid[i][j] + max;
        }

#### [分割回文串][Link 6] ####

回溯法思考的步骤：

1、画递归树；

2、根据自己画的递归树编码。

![img][img 12]

方法一：回溯

import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.Deque;
    import java.util.List;
    
    public class Solution {
        
    
        public List<List<String>> partition(String s) {
        
            int len = s.length();
            List<List<String>> res = new ArrayList<>();
            if (len == 0) {
        
                return res;
            }
    
            // Stack 这个类 Java 的文档里推荐写成 Deque<Integer> stack = new ArrayDeque<Integer>();
            // 注意：只使用 stack 相关的接口
            Deque<String> stack = new ArrayDeque<>();
            backtracking(s, 0, len, stack, res);
            return res;
        }
    
        /**
         * @param s
         * @param start 起始字符的索引
         * @param len   字符串 s 的长度，可以设置为全局变量
         * @param path  记录从根结点到叶子结点的路径
         * @param res   记录所有的结果
         */
        private void backtracking(String s, int start, int len, Deque<String> path, List<List<String>> res) {
        
            if (start == len) {
        
                res.add(new ArrayList<>(path));
                return;
            }
    
            for (int i = start; i < len; i++) {
        
    
                // 因为截取字符串是消耗性能的，因此，采用传子串索引的方式判断一个子串是否是回文子串
                // 不是的话，剪枝
                if (!checkPalindrome(s, start, i)) {
        
                    continue;
                }
    
                path.addLast(s.substring(start, i + 1));
                backtracking(s, i + 1, len, path, res);
                path.removeLast();
            }
        }
    
        /**
         * 这一步的时间复杂度是 O(N)，因此，可以采用动态规划先把回文子串的结果记录在一个表格里
         *
         * @param str
         * @param left  子串的左边界，可以取到
         * @param right 子串的右边界，可以取到
         * @return
         */
        private boolean checkPalindrome(String str, int left, int right) {
        
            // 严格小于即可
            while (left < right) {
        
                if (str.charAt(left) != str.charAt(right)) {
        
                    return false;
                }
                left++;
                right--;
            }
            return true;
        }
    }

方法二：回溯的优化

import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.Deque;
    import java.util.List;
    import java.util.Stack;
    
    public class Solution {
        
    
        public List<List<String>> partition(String s) {
        
            int len = s.length();
            List<List<String>> res = new ArrayList<>();
            if (len == 0) {
        
                return res;
            }
    
            // 预处理
            // 状态：dp[i][j] 表示 s[i][j] 是否是回文
            boolean[][] dp = new boolean[len][len];
            // 状态转移方程：在 s[i] == s[j] 的时候，dp[i][j] 参考 dp[i + 1][j - 1]
            for (int right = 0; right < len; right++) {
        
                // 注意：left <= right 取等号表示 1 个字符的时候也需要判断
                for (int left = 0; left <= right; left++) {
        
                    if (s.charAt(left) == s.charAt(right) && (right - left <= 2 || dp[left + 1][right - 1])) {
        
                        dp[left][right] = true;
                    }
                }
            }
    
            Deque<String> stack = new ArrayDeque<>();
            backtracking(s, 0, len, dp, stack, res);
            return res;
        }
    
        private void backtracking(String s,
                                  int start,
                                  int len,
                                  boolean[][] dp,
                                  Deque<String> path,
                                  List<List<String>> res) {
        
            if (start == len) {
        
                res.add(new ArrayList<>(path));
                return;
            }
    
            for (int i = start; i < len; i++) {
        
                // 剪枝
                if (!dp[start][i]) {
        
                    continue;
                }
                path.addLast(s.substring(start, i + 1));
                backtracking(s, i + 1, len, dp, path, res);
                path.removeLast();
            }
        }
    }

#### [子集][Link 7] ####

方法一：迭代法实现子集枚举

class Solution {
        
        List<Integer> t = new ArrayList<Integer>();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
    
        public List<List<Integer>> subsets(int[] nums) {
        
            int n = nums.length;
            for (int mask = 0; mask < (1 << n); ++mask) {
        
                t.clear();
                for (int i = 0; i < n; ++i) {
        
                    if ((mask & (1 << i)) != 0) {
        
                        t.add(nums[i]);
                    }
                }
                ans.add(new ArrayList<Integer>(t));
            }
            return ans;
        }
    }

方法二：递归法实现子集枚举

class Solution {
        
        List<Integer> t = new ArrayList<Integer>();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
    
        public List<List<Integer>> subsets(int[] nums) {
        
            dfs(0, nums);
            return ans;
        }
    
        public void dfs(int cur, int[] nums) {
        
            if (cur == nums.length) {
        
                ans.add(new ArrayList<Integer>(t));
                return;
            }
            t.add(nums[cur]);
            dfs(cur + 1, nums);
            t.remove(t.size() - 1);
            dfs(cur + 1, nums);
        }
    }

[Link 1]: https://leetcode-cn.com/problems/eight-queens-lcci/
[N]: https://leetcode-cn.com/problems/n-queens/
[N_ II]: https://leetcode-cn.com/problems/n-queens-ii/
[Link 2]: https://leetcode-cn.com/problems/combinations/
[img]: /images/20221014/0a19a537f5b74f23993a1b5801cc3a48.png
[img 1]: /images/20221014/1c9b62f9f12b4ccdb9893def657665ef.png
[img 2]: /images/20221014/d3e69b872b0d4d90983348f26221c1a5.png
[Link 3]: https://leetcode-cn.com/problems/combination-sum/
[img 3]: /images/20221014/22c216a8bade42bfbffc671e66860f15.png
[_ II]: https://leetcode-cn.com/problems/combination-sum-ii/
[img 4]: /images/20221014/e314c49d5adc4225b7dc549ba91bfe6f.png
[img 5]: /images/20221014/8a3c2e796b334ecc875f328b0c14eec0.png
[III]: https://leetcode-cn.com/problems/combination-sum-iii/
[img 6]: /images/20221014/cdc69c3401cd4d47ae9559c69ed98086.png
[img 7]: /images/20221014/d5cbe7e506c54095afbfb0147a867def.png
[Link 4]: https://leetcode-cn.com/problems/permutations/
[img 8]: /images/20221014/dab387190c5a43a9a4e170ff97732e82.png
[II]: https://leetcode-cn.com/problems/permutations-ii/
[img 9]: /images/20221014/ecf5190b01c346e9ab8113d29d14a7ec.png
[Link 5]: https://leetcode-cn.com/problems/path-with-maximum-gold/
[img 10]: /images/20221014/d25e462e79414f82a049ef96cc1ed698.png
[img 11]: /images/20221014/6ca9920ca0d147528c99c7063739c88f.png
[Link 6]: https://leetcode-cn.com/problems/palindrome-partitioning/
[img 12]: /images/20221014/b538dae07ac44a18a3655e5dff6865d7.png
[Link 7]: https://leetcode-cn.com/problems/subsets/