14.27 Generate Valid Angle Bracket Sequences

14.27.1 Problem Metadata

14.27.2 Description

Given n, return all valid sequences of n pairs of '<' and '>' with proper nesting. A valid sequence ensures that every opening bracket '<' has a corresponding closing bracket '>' and they are properly nested.

This problem is analogous to generating all combinations of well-formed parentheses, but using angle brackets instead.

14.27.3 Examples

Example 1:

Input: n = 1
Output: ["<>"]
Explanation: With one pair of angle brackets, the only valid nesting is "<>".

Example 2:

Input: n = 2
Output: ["<<>>", "<><>"]
Explanation: There are two valid sequences for two pairs:
  - "<<>>" — nest the second pair inside the first
  - "<><>" — place the two pairs side by side

Example 3:

Input: n = 3
Output: ["<<<>>>", "<<><>>", "<<>><>", "<><<>>", "<><><>"]
Explanation: For three pairs, there are 5 valid sequences (Catalan number C(3) = 5):
  - "<<<>>>" — all nested
  - "<<><>>" — outer pair contains two side-by-side pairs
  - "<<>><>" — first two pairs nested, third separate
  - "<><<>>" — first separate, last two nested
  - "<><><>" — all side by side

14.27.4 Constraints

  • \(0 \le n \le 12\)
  • n is an integer

14.27.5 Solution - Backtracking

14.27.5.1 Walkthrough

This problem uses the 2-dimensional traversal mental model of backtracking, specifically using Pattern 2 (Pass-by-Value) (see Pattern 2: Pass-by-Value):

  • Outer dimension (recursion parameters): open and close counts - controls the depth in the decision tree (how many total brackets we’ve placed, ranging from 0 to 2n)
  • Inner dimension (implicit binary choice): At each depth, we have up to 2 choices: add < or add > (conditional on validity rules)

The backtracking explores a conceptual 2D grid where: - Rows represent depth/position in the sequence (character 0 to character 2n-1) - Columns represent the binary choice at each position (try <, then try >) - Each cell in the grid represents a state: (position, open_count, close_count)

This 2D traversal systematically explores all valid bracket sequences by making sequential binary decisions at each position.

Core Idea: At each step, decide whether to add < or > based on: 1. How many opening brackets < have been used (tracked by open) 2. How many closing brackets > have been used (tracked by close) 3. Two simple rules that ensure we never create invalid sequences

The Two Rules: 1. Can add <: Only if we haven’t used all n opening brackets yet (open < n) 2. Can add >: Only if there are unmatched opening brackets (close < open)

The second rule is crucial: it prevents sequences like >< or >><< because you can only add > when there’s a preceding unmatched < to pair with.

Example walkthrough with n = 2:

Start: backtrack("", open=0, close=0, n=2)

1. Add '<': backtrack("<", open=1, close=0, n=2)
   1.1. Add '<': backtrack("<<", open=2, close=0, n=2)
        1.1.1. Can't add '<' (open == n)
        1.1.2. Add '>': backtrack("<<>", open=2, close=1, n=2)
               1.1.2.1. Can't add '<' (open == n)
               1.1.2.2. Add '>': backtrack("<<>>", open=2, close=2, n=2)
                        Base case reached! Add "<<>>" to result ✓

   1.2. Add '>': backtrack("<>", open=1, close=1, n=2)
        1.2.1. Add '<': backtrack("<><", open=2, close=1, n=2)
               1.2.1.1. Can't add '<' (open == n)
               1.2.1.2. Add '>': backtrack("<><>", open=2, close=2, n=2)
                        Base case reached! Add "<><>" to result ✓

Result: ["<<>>", "<><>"]

Why this never generates invalid sequences: - We start with empty string (valid) - Adding < when open < n keeps it valid (just adds an unmatched opener) - Adding > when close < open keeps it valid (closes an existing opener) - When open == close == n, we have exactly n matched pairs

Contrast with the initial approach: Your original solution generated candidates and validated them afterward with isBalancedParen(). The optimized approach ensures validity during construction, eliminating the need for post-validation and avoiding exploration of invalid paths entirely.

14.27.5.2 Analysis

  • Time Complexity: O(4^n / √n)
    • This is the nth Catalan number \(C_n = \frac{1}{n+1}\binom{2n}{n} \approx \frac{4^n}{n\sqrt{\pi n}}\)
    • Each valid sequence requires O(n) time to build (concatenating characters)
    • There are exactly \(C_n\) valid sequences for n pairs
    • Examples: C(1)=1, C(2)=2, C(3)=5, C(4)=14, C(5)=42
  • Space Complexity: O(n)
    • Recursion depth is at most 2n (we add 2n characters total)
    • Each recursive call adds one frame to the call stack
    • The current string grows to length 2n in the deepest recursion
    • Output space O(4^n / √n) for storing all valid sequences is not counted in auxiliary space complexity

14.27.5.3 Implementation Steps

  1. Initialize result lc-list: Create an empty ArrayList to store all valid sequences
  2. Call backtracking helper: Start with empty string, open = 0, close = 0, and target n
  3. Base case in backtrack:
    • When open == n AND close == n, we’ve used all brackets
    • Add the completed sequence to result lc-list
    • Return to explore other branches
  4. Recursive case 1 - Try adding <:
    • Check if open < n (haven’t used all opening brackets)
    • If true, recurse with current + "<", increment open count
  5. Recursive case 2 - Try adding >:
    • Check if close < open (there are unmatched opening brackets)
    • If true, recurse with current + ">", increment close count
  6. Return result: After backtracking completes, return the lc-list of all valid sequences

14.27.5.4 Code - Java

class Result {

    /*
     * Complete the 'generateAngleBracketSequences' function below.
     *
     * The function is expected to return a STRING_ARRAY.
     * The function accepts INTEGER n as parameter.
     */

    public static List<String> generateAngleBracketSequences(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result, "", 0, 0, n);
        return result;
    }

    private static void backtrack(List<String> result, String current, int open, int close, int n) {
        // Base case: if we've used all n pairs of brackets
        if (open == n && close == n) {
            result.add(current);
            return;
        }

        // Try adding '<' if we haven't used all n opening brackets
        if (open < n) {
            backtrack(result, current + "<", open + 1, close, n);
        }

        // Try adding '>' if there are unmatched opening brackets
        if (close < open) {
            backtrack(result, current + ">", open, close + 1, n);
        }
    }

}