电话号码字母组合与括号生成

电话号码的字母组合（LeetCode 17）

数字2-9映射字母，返回所有可能的字母组合。

private static final String[] MAP = {
    "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};

public List<String> letterCombinations(String digits) {
    List<String> res = new ArrayList<>();
    if (digits.isEmpty()) return res;
    backtrack(digits, 0, new StringBuilder(), res);
    return res;
}

private void backtrack(String digits, int idx, StringBuilder cur, List<String> res) {
    if (idx == digits.length()) {
        res.add(cur.toString());
        return;
    }
    for (char c : MAP[digits.charAt(idx) - '0'].toCharArray()) {
        cur.append(c);
        backtrack(digits, idx + 1, cur, res);
        cur.deleteCharAt(cur.length() - 1);
    }
}

时间复杂度：O(4^n × n)，n 为数字个数，4 是最大映射数。

括号生成（LeetCode 22）

生成 n 对有效括号的所有组合。

核心约束

• 左括号数 < n 才能加左括号
• 右括号数 < 已加左括号数 才能加右括号

public List<String> generateParenthesis(int n) {
    List<String> res = new ArrayList<>();
    backtrack(n, 0, 0, new StringBuilder(), res);
    return res;
}

private void backtrack(int n, int open, int close, StringBuilder cur, List<String> res) {
    if (cur.length() == 2 * n) {
        res.add(cur.toString());
        return;
    }
    if (open < n) {
        cur.append('(');
        backtrack(n, open + 1, close, cur, res);
        cur.deleteCharAt(cur.length() - 1);
    }
    if (close < open) {
        cur.append(')');
        backtrack(n, open, close + 1, cur, res);
        cur.deleteCharAt(cur.length() - 1);
    }
}

关键洞察：无需校验，约束本身保证合法。结果数等于卡特兰数 Cn = C(2n,n)/(n+1)。

全排列（LeetCode 46/47）

46：无重复元素

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    backtrack(nums, used, new ArrayList<>(), res);
    return res;
}

private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
    if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true;
        path.add(nums[i]);
        backtrack(nums, used, path, res);
        path.removeLast();
        used[i] = false;
    }
}

47：有重复元素（去重）

public List<List<Integer>> permuteUnique(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    backtrack(nums, used, new ArrayList<>(), res);
    return res;
}

private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
    if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        // 同层：当前元素与前一个相同且前一个未被使用（说明在同层已搜索过）
        if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
        used[i] = true;
        path.add(nums[i]);
        backtrack(nums, used, path, res);
        path.removeLast();
        used[i] = false;
    }
}

子集（LeetCode 78/90）

78：无重复

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

private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path));   // 每个节点都是一个子集
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(nums, i + 1, path, res);
        path.removeLast();
    }
}

90：有重复

排序后，同层跳过重复 if (i > start && nums[i] == nums[i-1]) continue;

回溯模板总结

backtrack(参数):
    if 终止条件: 收集结果; return
    for 选择 in 选择列表:
        剪枝（提前终止）
        做选择（加入路径）
        backtrack(下一层)
        撤销选择