面试经典 150 题-回溯

LeetCode 面试经典 150 题-回溯

从今天开始练习ACM模式的题目，从牛客上找力扣对应或相似的题目。

字符串组合

穷举

1. 使用treeset去重，重定义比较函数。
2. 外层循环枚举字符串长度，内层循环枚举起始位置，加入集合。

import java.util.*;


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        // 用于存储所有的组合，使用Set来去重
        Set<String> set = new TreeSet<>(new Comparator<String>(){
            public int compare(String s1, String s2) {
                if (s1.length() == s2.length()) {
                    return s1.compareTo(s2);
                } else {
                    return s1.length() - s2.length();
                }
            }
        });
        
        // 生成所有相邻字符的组合
        int n = s.length();
        // 枚举字符串长度
        for (int len = 1; len <= n; len++) {
            // 枚举起始位置
            for (int start = 0; start <= n - len; start++) {
                set.add(s.substring(start, start + len));
            }
        }
        // 输出结果，以空格分隔
        System.out.println(String.join(" ", set));
    }
}

• 时间复杂度：生成所有字符串$O(n^2)$，排序$O(n^2 \log (n^2))$，因为最多生成$n^2$个字符串。
• 空间复杂度：$O(n^2)$

电话号码的字母组合

回溯法

这道题的核心是 回溯法（Backtracking），类似于一个多叉树的遍历问题。

步骤：

构建映射关系：用哈希表存储 数字 -> 字母 的映射，例如 '2' -> "abc"，'3' -> "def"。
回溯递归：
    遍历输入 digits，对每个数字对应的字母 逐个尝试。
    递归深入下一层，直到构造完所有的字母组合。
    递归结束后回溯（撤销当前选择），尝试下一个可能的组合。
边界情况：输入为空时，返回空列表。

package backtrack;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LetterCombinations {
    public static void main(String[] args) {
        LetterCombinations solver = new LetterCombinations();

        // 测试案例
        System.out.println(solver.letterCombinations("23"));
        System.out.println(solver.letterCombinations("7"));
        System.out.println(solver.letterCombinations(""));
        System.out.println(solver.letterCombinations("9"));
    }

    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return res;
        }
        Map<Character, String> map = new HashMap<>() {{
            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, digits, map,0, new StringBuffer());
        return res;
    }

    public void backtrack(List<String> res, String digits, Map<Character, String> map, int index, StringBuffer combination) {
        if (index == digits.length()) {
            res.add(combination.toString());
        } else {
            char ch = digits.charAt(index);
            String s = map.get(ch);
            for (int i = 0; i < s.length(); i++) {
                combination.append(s.charAt(i));
                backtrack(res, digits, map, index + 1, combination);
                combination.deleteCharAt(combination.length() - 1);
            }
        }
    }
}

• 时间复杂度：$O(3^m * 4^n)$
• 空间复杂度：O(m+n)，空间复杂度主要取决于哈希表以及回溯过程中的递归调用层数，哈希表的大小与输入无关，可以看成常数，递归调用层数最大为m+n。

组合

回溯法

首先，从 1 到 n 中选择一个数字，并递归地继续选择下一个数字，直到组合的大小达到 k。当组合完成时，将其添加到结果中。在递归过程中，通过回溯移除最后添加的元素，回到上一步继续尝试其他可能的组合。这样能够生成所有从 1 到 n 中选择 k 个数的组合。

package backtrack;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Combinations {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();

        Combinations solution = new Combinations();
        List<List<Integer>> res = solution.combine(n, k);
        for (List<Integer> list : res) {
            System.out.println(list);
        }
    }

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(res, new ArrayList<>(), 1, n, k);
        return res;
    }

    public void backtrack(List<List<Integer>> res, List<Integer> combination, int index, int n, int k) {
        // 递归结束
        if (combination.size() == k) {
            res.add(new ArrayList<>(combination));
        } else {
            for (int i = index; i <= n; i++) {
                combination.add(i);
                backtrack(res, combination, i + 1, n, k);
                combination.remove(combination.size() - 1);
            }
        }
    }
}

• 时间复杂度：$O(C(n,k) \times k)$，组合的总数为 C(n,k) = n!/(k!(n-k)!)，对于每个组合，我们需要O(k)的时间来创建新的列表并添加到结果中。
• 空间复杂度：O(k)，递归的最大深度为k，因为我们需要选择k个数。

全排列

回溯法

首先，将输入数组 nums 转换为列表 cur。然后，通过递归函数 backtrack 实现回溯算法生成所有排列。在每一层递归中，遍历从当前索引 index 到列表末尾的所有元素，并通过交换来生成新的排列。每当递归到达 cur.size() 时，表示一个完整的排列已生成，添加到结果 res 中。回溯过程中使用 Collections.swap 恢复元素顺序，以便探索其他排列。

package backtrack;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Permutations {
    public static void main(String[] args) {
        Permutations permutations = new Permutations();
        List<List<Integer>> res = permutations.permute(new int[]{1, 2, 3});
        System.out.println(res);
    }
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            cur.add(nums[i]);
        }
        backtrack(res, cur, 0);
        return res;
    }

    public void backtrack(List<List<Integer>> res, List<Integer> cur, int index) {
        // 递归结束
        if (index == cur.size()) {
            res.add(new ArrayList<Integer>(cur));
        } else {
            for (int i = index; i < cur.size(); i++) {
                Collections.swap(cur, index, i);
                backtrack(res, cur, index + 1);
                Collections.swap(cur, index, i);
            }
        }
    }
}

• 时间复杂度：O(n * n!)，backtrack的调用次数是O(n!)，需要将当前答案使用O(n)的时间复制到答案数组中。
• 空间复杂度：O(n)，递归栈空间，不计返回值空间。

N皇后II

回溯法

定义每列、左上-右下、右上-左下标记数组，尝试对于每一行放置皇后，遍历每一列，计算对角线下标，然后递归下一行，再回溯。

package backtrack;

import java.util.Scanner;

public class nqueens {
    private int ans;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        nqueens solution = new nqueens();
        int n = sc.nextInt();
        System.out.println(solution.totalNQueens(n));
    }

    public int totalNQueens(int n) {
        boolean[] col = new boolean[n];
        boolean[] diag1 = new boolean[n * 2 - 1];
        boolean[] diag2 = new boolean[n * 2 - 1];
        dfs(0, col, diag1, diag2);
        return ans;
    }

    private void dfs(int r, boolean[] col, boolean[] diag1, boolean[] diag2) {
        int n = col.length;
        // 找到一个合法方案
        if (r == n) {
            ans++;
            return;
        }
        // 遍历当前行每一列
        for (int c = 0; c < n; c++) {
            // 转换成合法索引
            int rc = r - c + n - 1;
            if (!col[c] && !diag1[r + c] && !diag2[rc]) {
                col[c] = diag1[r + c] = diag2[rc] = true;   // 在(r,c)放置皇后
                dfs(r + 1, col, diag1, diag2);              // 放置下一行
                col[c] = diag1[r + c] = diag2[rc] = false;  // 回溯
            }
        }
    }
}

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

括号生成

回溯法

1. 回溯函数参数：结果集和当前括号组合，左括号剩余数和右括号剩余数。
2. 递归结束条件：左括号剩余数和右括号剩余数都是0.
3. 如果当前左括号剩余数大于0，那么可以选择左括号，左括号剩余数-1再递归遍历，回溯；如果当前左括号剩余数小于右括号剩余数，那么可以选择右括号，右括号剩余数-1再递归遍历，回溯。
4. 返回结果集。

package backtrack;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class ParentTheses {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        ParentTheses p = new ParentTheses();
        List<String> ans = p.generateParenthesis(n);
        System.out.println(ans);
    }

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

    public void backtrack(List<String> ans, StringBuffer s, int left, int right) {
        // 递归结束
        if (left == 0 && right == 0) {
            ans.add(s.toString());
            return;
        }
        // 选择左括号
        if (left > 0) {
            s.append('(');
            backtrack(ans, s, left - 1, right);
            s.deleteCharAt(s.length() - 1);
        }
        // 选择右括号
        if (right > left) {
            s.append(')');
            backtrack(ans, s, left, right - 1);
            s.deleteCharAt(s.length() - 1);
        }
    }
}

• 时间复杂度：$\frac{4^n}{\sqrt{n}}$
• 空间复杂度：O(n)，结果不计入空间。

单词搜索

回溯

1. 对每一个位置作为单词起始进行搜索，如果搜索到了就可以返回true；
2. 回溯函数参数：网格，单词，当前搜索位置行列坐标，单词索引；
3. 递归结束条件：单词索引遍历到最后；
4. 剪枝：超出边界、当前位置已访问过、当前位置字符不等于当前单词字符；
5. 对上下左右四个方向进行搜索，回溯；
6. 返回结果。

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

        // 搜索每一个位置
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (backtrack(board, word, visited, i, j, 0)) {
                    return true;
                }
            }
        }

        return false;
    }

    public boolean backtrack(char[][] board, String word, boolean[][] visited, 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] || board[i][j] != word.charAt(index)) {
            return false;
        }

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

        return res;
    }
}

• 时间复杂度：$O(mn \cdot 3^L)$，除了第一次可以进入4个分支以外，其余时间我们最多会进入3个分支。
• 空间复杂度：O(m * n + L)。