Letter Combinations and Parenthesis Generation

Letter Combinations of a Phone Number (LeetCode 17)

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

private static final String[] DIGIT_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 index, StringBuilder current, List<String> res) {
    if (index == digits.length()) {
        res.add(current.toString());
        return;
    }
    
    String letters = DIGIT_MAP[digits.charAt(index) - '0'];
    for (char c : letters.toCharArray()) {
        current.append(c);
        backtrack(digits, index + 1, current, res);
        current.deleteCharAt(current.length() - 1); // Backtrack
    }
}

Time Complexity: $O(4^N \cdot N)$, where $N$ is the length of digits and $4$ is the maximum mapping length.

Generate Parentheses (LeetCode 22)

Given $n$ pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Core Constraints

• Add an opening parenthesis if openCount < n.
• Add a closing parenthesis if closeCount < openCount.

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 current, List<String> res) {
    if (current.length() == 2 * n) {
        res.add(current.toString());
        return;
    }
    
    if (open < n) {
        current.append('(');
        backtrack(n, open + 1, close, current, res);
        current.deleteCharAt(current.length() - 1);
    }
    
    if (close < open) {
        current.append(')');
        backtrack(n, open, close + 1, current, res);
        current.deleteCharAt(current.length() - 1);
    }
}

Insight: No explicit validity check is required; the constraints themselves ensure only well-formed parentheses are generated. The total count matches the Catalan number $C_n = \frac{1}{n+1} \binom{2n}{n}$.

Permutations (LeetCode 46/47)

No Duplicates (46)

public 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;
    }
}

With Duplicates (47)

Sort first, then skip duplicates at the same tree level.

public 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;
        // Horizontal deduplication: if current is same as prev AND prev was already explored
        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;
    }
}

Subsets (LeetCode 78/90)

No Duplicates (78)

private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path)); // Every valid path is a subset
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(nums, i + 1, path, res);
        path.removeLast();
    }
}

With Duplicates (90)

Apply the same horizontal pruning: if (i > start && nums[i] == nums[i-1]) continue; after sorting.

Backtracking Pattern Reference

1. Terminate: Check if path is a valid solution.
2. Collect: Save a copy of the path.
3. Iterate: Loop through possible candidates.
4. Prune: Skip branches that violate constraints or repeat results.
5. Revert: Undo choice after returning from recursion. 筋