22. Generate Parentheses

Build the string one bracket at a time, tracking how many '(' and ')' have been used. You may add '(' while some opens remain, and ')' only while there are unmatched opens — this guarantees every generated string is valid.

Idea

Instead of generating all bracket strings and filtering, we only ever build valid prefixes. Two rules keep every partial string well-formed:

• Add ( if we still have opens left (open < n).
• Add ) only if it would close an existing open (close < open).

When the string reaches length 2n, it's a complete valid combination.

Algorithm

backtrack(cur, open, close):

1. If len(cur) == 2n, record cur.
2. If open < n, recurse with cur + '(', open+1.
3. If close < open, recurse with cur + ')', close+1.

Worked example: n = 3

Exploring opens-first yields, in order: ((())), (()()), (())(), ()(()), ()()().

Complexity

• Time: O(4^n / √n) — the nth Catalan number of valid strings.
• Space: O(n) recursion depth (plus the output).

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

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

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