LeetCode 热题 100-回溯法

从这里开始要试着用java刷题了！

全排列

回溯法

使用标记数组来处理填过的数是一个很直观的思路，为减少空间复杂度，将题目给定的 n 个数的数组 nums 划分成左右两个部分，左边的表示已经填过的数，右边表示待填的数，我们在回溯的时候只要动态维护这个数组即可。

• 递归终止条件，index == nums.size()。
• 递归选择：动态维护数组，将i与index交换，然后递归填下一个数，结束后再换回来。

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> path = new ArrayList<Integer>();
        for (int num : nums) {
            path.add(num);
        }

        backtrack(path, 0, res);
        return res;
    }

    public void backtrack(List<Integer> path, int index, List<List<Integer>> res) {
        // 加入结果集
        if (index == path.size()) {
            res.add(new ArrayList<Integer>(path));
        } else {
            for (int i = index; i < path.size(); i++){
                Collections.swap(path, index, i);
                backtrack(path, index + 1, res);
                Collections.swap(path, index, i);
            }
        }
    }
}

• 时间复杂度：$O(n \times n!)$，递归的调用次数是 n!，即全排列的数量。对于每个叶子节点，复制 path 的时间复杂度是 O(n)。
• 空间复杂度：O(n)，除答案数组以外，递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，这里可知递归调用深度为 O(n)。

子集

回溯法

• 递归结束条件：index == nums.size()。
• 递归选择：每次可以选择加入或不加入当前元素。

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        backtrack(nums, 0, path, res);
        return res;
    }

    public void backtrack (int[] nums, int index, List<Integer> path, List<List<Integer>> res) {
        // 递归结束
        if (index == nums.length) {
            res.add(new ArrayList<Integer>(path));
            return;
        }

        // 不加入当前元素
        backtrack(nums, index + 1, path, res);

        // 加入当前元素
        path.add(nums[index]);
        backtrack(nums, index + 1, path, res);
        path.remove(path.size() - 1);
    }
}

• 时间复杂度：$O(n \times 2^n)$，一共$2^n$个状态，每种状态需要 O(n) 的时间来构造子集。
• 空间复杂度：O(n)，递归栈空间。

迭代

0/1序列对应的二进制数即$[0, 2^n-1]$，可以枚举mask，构造出所有的子集。外部循环是所有可能的子集个数，内部循环指示当前子集的状态，如果mask的第i位为1，则当前数字在子集中，如果是0则不在。

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

        return res;
    }
}

• 时间复杂度：$O(n \times 2^n)$
• 空间复杂度：O(n)，临时数组的代价。

电话号码的字母组合

回溯法

1. 首先使用哈希表存储每个数字对应的所有可能的字母，然后进行回溯操作。
2. 回溯过程中维护一个字符串，表示已有的字母排列。该字符串初始为空。每次取电话号码的一位数字，从哈希表中获得该数字对应的所有可能的字母，并将其中的一个字母插入到已有的字母排列后面，然后继续处理电话号码的后一位数字，直到处理完电话号码中的所有数字，即得到一个完整的字母排列。
3. 然后进行回退操作，遍历其余的字母排列。

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<String>();
        // 边界处理
        if (digits.length() == 0) {
            return res;
        }
        // 创建哈希表存储
        Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};

        backtrack(res, phoneMap, digits, 0, new StringBuffer());
        return res;
    }

    public void backtrack (List<String> res, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
        // 递归结束
        if (index == digits.length()) {
            res.add(combination.toString());
            return;
        }

        // 对于每一个数字
        char digit = digits.charAt(index);
        String letters = phoneMap.get(digit);
        for (char ch : letters.toCharArray()) {
            combination.append(ch);
            backtrack(res, phoneMap, digits, index + 1, combination);
            combination.deleteCharAt(index);
        }
    }
}

• 时间复杂度：$O(3^m \times 4^n)$，输入包含 m 个对应 3 个字母的数字和 n 个对应 4 个字母的数字。
• 空间复杂度：O(m+n)，递归调用层数最大为 m+n。

组合总和

回溯法

递归终止条件：当前和等于目标，或index到结尾。

递归选择：如果不选择当前元素，就递归下一个元素；如果选择当前数字后的和不大于目标，就将其加入当前数组，并继续递归当前元素（因为可以重复选择），然后再将该元素取出，回溯。

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(candidates, 0, target, 0, res, path);
        return res;
    }

    public void dfs(int[] candidates, int index, int target, int curSum, List<List<Integer>> res, List<Integer> path) {
        // 递归结束
        if (curSum == target) {
            res.add(new ArrayList<Integer>(path));
            return;
        }
        if (index == candidates.length) {
            return;
        }

        // 不选择当前元素
        dfs(candidates, index + 1, target, curSum, res, path);

        // 选择当前元素
        if (curSum + candidates[index] <= target){
            path.add(candidates[index]);
            dfs(candidates, index, target, curSum + candidates[index], res, path);  // 可重复选择
            path.remove(path.size() - 1);
        }
    }
}

• 时间复杂度：$O(2^n \cdot \frac{target}{min(candidates)})$
  • 深度：递归的深度在最坏情况下是$O(\frac{target}{min(candidates)})$，因为每次选择一个元素时，目标值 target 会减去某个候选元素的值，直到 curSum 达到 target。
  • 宽度：搜索树的每一层最多有 $O(2^n)$ 分支，其中 nn 是 candidates 的长度。
• 空间复杂度：O(target)，返回值不计入。path 长度和递归深度至多为 O(target)。

剪枝优化：可以对candidates进行排序，这样后面的数字就无需再进行判断。

括号生成

回溯法

递归结束：左括号剩余数=右括号剩余数=0

递归选择：用变量记录当前的左括号和右括号剩余数，如果当前左括号剩余数大于0那就可以继续生成左括号，如果右括号数剩余数大于左括号剩余数那就可以生成右括号。

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<String>();
        dfs(n, n, new StringBuffer(), res);
        return res;
    }

    public void dfs(int left, int right, StringBuffer str, List<String> res){
        // 递归结束
        if (left == 0 && right == 0) {
            res.add(str.toString());
        }

        // 选择左括号
        if (left > 0) {
            str.append('(');
            dfs(left-1, right, str, res);
            str.deleteCharAt(str.length() - 1);
        }

        // 选择右括号
        if (right > left) {
            str.append(')');
            dfs(left, right-1, str, res);
            str.deleteCharAt(str.length() - 1);
        }
    }
}

• 时间复杂度：分析回溯问题的时间复杂度，有一个通用公式：路径长度×搜索树的叶子数。第n个卡特兰数$O(\frac{4^n}{n\sqrt{n}})$,在回溯过程中，每个答案需要 O(n) 的时间复制到答案数组中，因此时间复杂度为$O(\frac{4^n}{\sqrt{n}})$。
• 空间复杂度：O(n)，递归栈深度。

单词搜索

回溯法

1. 定义一个标记数组，标记当前位置是否访问过。
2. 遍历板子的每个位置，每次从单词的第一个字符开始进行回溯搜索。
3. 如果当前索引到最后，则递归结束，找到了整个单词，返回true。
4. 否则检查边界条件、当前位置是否访问过、是否匹配，如果有一个不满足就返回false。
5. 标记当前位置已访问过，继续搜索上下左右四个位置。
6. 回溯，将当前位置标记为false。
7. 返回递归搜索的结果。

class Solution {
    boolean[][] visited;

    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        visited = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }

        return false;
    }

    public boolean dfs(char[][] board, String word, int i, int j, int index) {
        // 找到单词
        if (index == word.length()) {
            return true;
        }

        // 超出边界或不匹配
        int m = board.length;
        int n = board[0].length;
        if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] == true || board[i][j] != word.charAt(index)) {
            return false;
        }

        // 上下左右四个方向搜索
        visited[i][j] = true;
        boolean res = dfs(board, word, i-1, j, index + 1) || dfs(board, word, i+1, j, index + 1) || dfs(board, word, i, j-1, index + 1) || dfs(board, word, i, j+1, index + 1);

        visited[i][j] = false;  // 回溯
        return res;
    }
}

• 时间复杂度：$O(mn\cdot3^L)$，L是单词长度。除了递归入口，其余递归至多有 3 个分支（因为至少有一个方向是之前走过的），所以每次递归（回溯）的时间复杂度为$O(3^L)$。
• 空间复杂度：$O(m \times n + L)$

优化点：

1. 统计word中字母出现的次数，如果某个字母出现的次数比整个板子该字母出现的次数多，则直接返回false。
2. 设 word 的第一个字母在 board 中出现了 x 次，word 的最后一个字母在 board 中出现了 y 次。如果 y<x，我们可以把 word 反转，相当于从 word 的最后一个字母开始搜索，这样更容易在一开始就满足 board[i][j] != word[k]，不会往下递归，递归的总次数更少。

分割回文串

选或不选

• 递归结束：index == n。
• 是否要把 s[i] 当成分割出的子串的最后一个字符。注意 s[n−1] 一定是最后一个字符，一定要选。

class Solution {
    List<List<String>> res;
    List<String> path;
    public List<List<String>> partition(String s) {
        res = new ArrayList<>();
        path = new ArrayList<>();
        dfs(s, 0, 0);
        return res;
    }

    // 回溯
    public void dfs(String s, int index, int start) {
        int n = s.length();
        // 递归结束
        if (index == n) {
            res.add(new ArrayList<String>(path));
            return;
        }

        // 不选
        if (index < n - 1) {
            dfs(s, index + 1, start);
        }

        // 选
        if (isPalindrome(s, start, index)) {
            path.add(s.substring(start, index + 1));
            dfs(s, index + 1, index + 1);
            path.remove(path.size() - 1);
        }
    }

    // 判断是否是回文串
    public boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}

• 时间复杂度：$O(n2^n)$，每次都是选或不选，递归次数为一个满二叉树的节点个数，即$2^n$，再算上判断回文和加入答案时需要 O(n) 的时间。
• 空间复杂度：O(n)

枚举结束的位置

• 递归结束：index == n。
• 枚举结束位置：从index开始向后枚举

class Solution {
    List<List<String>> res;
    List<String> path;
    public List<List<String>> partition(String s) {
        res = new ArrayList<>();
        path = new ArrayList<>();
        dfs(s, 0);
        return res;
    }

    // 回溯
    public void dfs(String s, int index) {
        int n = s.length();
        // 递归结束
        if (index == n) {
            res.add(new ArrayList<String>(path));
            return;
        }

        // 枚举子串的位置
        for (int j = index; j < n; j++) {
            if (isPalindrome(s, index, j)) {
                path.add(s.substring(index, j + 1));
                dfs(s, j + 1);
                path.remove(path.size() - 1);
            }
        }
    }

    // 判断是否是回文串
    public boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}

• 时间复杂度：$O(n2^n)$
• 空间复杂度：O(n)

N皇后

回溯法

• 递归结束条件：index == n。
• 递归选择：如果当前位置放置皇后，不产生冲突，则放置，否则置空。

class Solution {
    List<List<String>> res;
    List<String> board;
    public List<List<String>> solveNQueens(int n) {
        res = new ArrayList<>();
        board = new ArrayList<>();
        String dots = String.join("", Collections.nCopies(n, "."));
        for (int i = 0; i < n; i++) {
            board.add(dots);
        }
        dfs(0);
        return res;
    }

    public void dfs(int row) {
        int n = board.size();
        // 递归结束
        if (row == n) {
            res.add(new ArrayList<String>(board));
            return;
        }
        // 逐列放置皇后
        for (int col = 0; col < n; col++) {
            if (isValid(row, col)) {
                String rowString = board.get(row);
                board.set(row, rowString.substring(0, col) + 'Q' + rowString.substring(col + 1));
                dfs(row + 1);
                board.set(row, rowString); // 回溯
            }
        }
    }

    public boolean isValid(int row, int col) {
        int n = board.size();
        // 检查行
        for (int i = 0; i < row; i++) {
            if (board.get(i).charAt(col) == 'Q') {
                return false;
            }
        }

        // 检查45度角
        for (int i = row-1, j = col-1; i >= 0 && j >= 0; i--, j--) {
            if (board.get(i).charAt(j) == 'Q') {
                return false;
            }
        }

        // 检查135度角
        for (int i = row-1, j = col+1; i >= 0 && j < n; i--, j++) {
            if (board.get(i).charAt(j) == 'Q') {
                return false;
            }
        }

        return true;
    }
}

• 时间复杂度：$O(n \cdot n!)$，决策为n!，每次判断是否合法为O(n)，实际运行时间会小于这个上界，因为很多分支会被提前剪掉。
• 空间复杂度：$O(n^2)$，递归深度是O(n)，board是$O(n^2)$。

空间优化:

• 可以使用位运算来表示皇后的位置，将空间复杂度优化到 O(N)
• 使用三个整数分别记录列、主对角线、副对角线的占用情况

时间优化:

• 当前的 isValid 检查可以通过位运算优化
• 可以维护已占用的列和对角线信息，避免重复检查

class Solution {
    private int n;
    private List<List<String>> res;
    private int cols;      // 列占用情况
    private int diag1;     // 主对角线占用情况
    private int diag2;     // 副对角线占用情况
    
    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        this.res = new ArrayList<>();
        this.cols = 0;
        this.diag1 = 0;
        this.diag2 = 0;
        
        dfs(0, new ArrayList<>());
        return res;
    }
    
    private void dfs(int row, List<String> board) {
        if (row == n) {
            res.add(new ArrayList<>(board));
            return;
        }
        
        for (int col = 0; col < n; col++) {
            // 使用位运算检查位置是否可用
            if (isAvailable(row, col)) {
                // 标记占用
                markQueen(row, col, true);
                // 构建当前行字符串
                char[] rowChars = new char[n];
                Arrays.fill(rowChars, '.');
                rowChars[col] = 'Q';
                board.add(new String(rowChars));
                
                dfs(row + 1, board);
                
                // 回溯
                board.remove(board.size() - 1);
                markQueen(row, col, false);
            }
        }
    }
    
    private boolean isAvailable(int row, int col) {
        return ((cols & (1 << col)) |
                (diag1 & (1 << (row + col))) |
                (diag2 & (1 << (row - col + n - 1)))) == 0;
    }
    
    private void markQueen(int row, int col, boolean place) {
        int val = place ? 1 : 0;
        cols ^= (1 << col);
        diag1 ^= (1 << (row + col));
        diag2 ^= (1 << (row - col + n - 1));
    }
}

• 时间复杂度：O(n!)
• 空间复杂度：O(n)