☕ DSA Java Articles

Topics › Recursion and Backtracking › Subsequences Pattern

Generate Parentheses

Medium TUF ID 876 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given n pairs of parentheses, generate every string of n opening and n closing brackets that is well-formed: reading left to right, no closing bracket appears before its matching opening bracket, and every bracket is matched by the end.

Constraints: 1 ≤ n ≤ 8. The number of answers is the n-th Catalan number: 1, 2, 5, 14, 42, 132, 429, 1430 for n = 1 .. 8.

Example 1

n = 3
answer = ["((()))", "(()())", "(())()", "()(())", "()()()"]

Example 2

n = 1
answer = ["()"]

This problem is the model for a whole family of “build a string one character at a time, but only make choices that can still lead to a valid answer” recursions. The pruning rule is simple enough to state in one sentence and strong enough that nothing is ever thrown away.

Approach 1: Brute force

Intuition. A string of length 2n over the alphabet { '(', ')' } is a sequence of 2n binary choices, so there are 2^(2n) of them. Generate them all, test each for well-formedness, keep the ones that pass. Counting from 0 to 2^(2n) - 1 and mapping bit 0 to '(' lists the strings in lexicographic order, since '(' precedes ')' in ASCII.

The validity test is the classic balance scan: keep a counter of unmatched '('; +1 on an opening bracket, -1 on a closing one. The string is well-formed if the counter never goes negative and ends at zero.

Algorithm.

  1. For mask = 0 .. 2^(2n) - 1, build the string whose i-th character is '(' if bit 2n - 1 - i of mask is 0, else ')'.
  2. Scan it with the balance counter; reject if the counter drops below 0 or does not end at 0.
  3. Collect the survivors.
static List<String> bruteForce(int n) {
    List<String> result = new ArrayList<>();
    int len = 2 * n;
    for (int mask = 0; mask < (1 << len); mask++) {
        char[] s = new char[len];
        for (int i = 0; i < len; i++) s[i] = ((mask >> (len - 1 - i)) & 1) == 0 ? '(' : ')';
        if (isBalanced(s)) result.add(new String(s));
    }
    return result;
}

static boolean isBalanced(char[] s) {
    int open = 0;
    for (char c : s) {
        open += (c == '(') ? 1 : -1;
        if (open < 0) return false;                      // a ')' with nothing to close
    }
    return open == 0;
}

Complexity. Time O(2^(2n) · n): 4^n strings, each scanned in O(n). Space O(n) besides the output.

For n = 8 this is 65536 strings of which only 1430 are valid; for larger n the ratio gets worse quickly, because the Catalan numbers grow like 4^n / n^1.5 while the candidates grow like 4^n.

Approach 2: Optimal, backtracking on two counters

Intuition. Build the string left to right, keeping two numbers: open, how many '(' have been placed, and close, how many ')'. At any point there are at most two moves, and each has a condition that is exactly what makes the final string valid:

The second rule guarantees the balance never goes negative, and the first guarantees we use exactly n of each, so when the length reaches 2n the string must be well-formed. Every leaf is an answer; the tree has no dead branches at all. Trying '(' first gives lexicographic order.

Algorithm.

  1. backtrack(current, open, close): if current.length() == 2n, record current and return.
  2. If open < n: append '(', recurse with open + 1, then remove the character.
  3. If close < open: append ')', recurse with close + 1, then remove the character.
static List<String> optimal(int n) {
    List<String> result = new ArrayList<>();
    backtrack(new StringBuilder(), 0, 0, n, result);
    return result;
}

static void backtrack(StringBuilder current, int open, int close, int n, List<String> result) {
    if (current.length() == 2 * n) {                     // base case: all 2n characters placed
        result.add(current.toString());
        return;
    }
    if (open < n) {                                      // choice 1: open another bracket
        current.append('(');
        backtrack(current, open + 1, close, n, result);
        current.deleteCharAt(current.length() - 1);      // undo before trying the other choice
    }
    if (close < open) {                                  // choice 2: close one, only if something is open
        current.append(')');
        backtrack(current, open, close + 1, n, result);
        current.deleteCharAt(current.length() - 1);
    }
}

Dry run for n = 2:

""  (0,0)
└── "("  (1,0)
    ├── "(("  (2,0)          open == n, only ')' allowed from here
    │   └── "(()"  (2,1)
    │       └── "(())"  ✓
    └── "()"  (1,1)          close == open, only '(' allowed
        └── "()("  (2,1)
            └── "()()"  ✓

Note the node "(" with (1, 0): ')' is allowed because close < open, and '(' is allowed because open < n, so it has two children. The root "" has only one child because close < open is false there.

Complexity. Time O(C(n) · n) where C(n) is the n-th Catalan number, about 4^n / (n^1.5 · sqrt(pi)): one leaf per answer and O(n) to copy each. Space O(n) for the recursion depth (2n frames) and the shared StringBuilder.

The deleteCharAt after each recursive call is the backtracking step. The builder is shared by every frame, so each frame must leave it exactly as it found it before trying the other choice.

Approach 3: Structural recursion by the first closing bracket

Intuition. A different way to see a well-formed string: its first character is '(', and that bracket is closed by some ')'. Everything strictly between them is itself well-formed, say with k pairs, and everything after the closing bracket is well-formed with the remaining n - 1 - k pairs. So

answers(n) = { "(" + A + ")" + B  :  A in answers(k), B in answers(n - 1 - k), 0 ≤ k < n }

and every well-formed string arises exactly once this way (the position of the first bracket’s partner is determined). This is the recurrence C(n) = sum of C(k) · C(n - 1 - k) that defines the Catalan numbers. Rather than recompute answers(k) many times, fill a table from 0 up to n.

Algorithm.

  1. table[0] = [""].
  2. For k = 1 .. n: for every split inside from 0 to k - 1, for every a in table[inside] and b in table[k - 1 - inside], add "(" + a + ")" + b to table[k].
  3. Return table[n].
static List<String> byClosure(int n) {
    List<List<String>> table = new ArrayList<>();        // table.get(k) = all balanced strings with k pairs
    table.add(List.of(""));
    for (int k = 1; k <= n; k++) {
        List<String> level = new ArrayList<>();
        for (int inside = 0; inside < k; inside++) {    // pairs inside the first bracket; k - 1 - inside follow it
            for (String a : table.get(inside)) {
                for (String b : table.get(k - 1 - inside)) level.add("(" + a + ")" + b);
            }
        }
        table.add(level);
    }
    return table.get(n);
}

Complexity. Time O(C(n) · n) for the final level plus the smaller levels before it, since each string is produced once by concatenation. Space O(sum of C(k) · k) for the table, which is dominated by the last level.

The output order differs from the other two approaches ("()()" comes before "(())" for n = 2), so the test sorts it before comparing. This approach is less common in interviews but is the one that generalises to counting (replace lists by sizes and you have the Catalan DP).

Edge cases and pitfalls