Generate Parentheses: Backtracking with Constraints

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, when n = 3, the output is ["((()))","(()())","(())()","()(())","()()()"].

This is LeetCode 22: Generate Parentheses, and it is one of the best problems for learning constrained backtracking. Unlike problems like Subsets or Permutations where every branch is valid, generate parentheses forces you to prune invalid branches as you build the string. Two simple counting rules are all you need, and once you see them, the solution writes itself.

Why this problem matters

Generate parentheses teaches you that backtracking is not just "try everything." It is "try everything that is valid." At each position in the string, you have at most two choices: add "(" or add ")". But not every choice is legal. If you have already used all n open parens, you cannot add another. If your close count already matches your open count, adding ")" would create an invalid prefix like "())". The algorithm builds only valid strings by enforcing two constraints at every recursive step.

This problem also shows up constantly in interviews because it tests whether you understand the structure of recursion. The recursion tree is a binary tree (two choices at each node), but the constraints prune it into an asymmetric shape. Being able to draw that tree and explain which branches get cut is exactly what interviewers look for.

The two pruning rules

The entire algorithm rests on two rules that decide which characters you can append at each step:

1. Add "(" if open is less than n. You still have open parens left to use.
2. Add ")" if close is less than open. There is at least one unmatched "(" to close. If close equals open, every open paren is already matched, and adding ")" would break the sequence.

That is it. These two rules guarantee that every string you build is well-formed. You never generate an invalid combination, and you never miss a valid one.

When open == n and close == n, the string has length 2n and is a complete, valid result. Record it and backtrack.

The backtracking solution

def generateParenthesis(n: int) -> list[str]:
    result = []

    def backtrack(current, open_count, close_count):
        if len(current) == 2 * n:
            result.append(current)
            return

        if open_count < n:
            backtrack(current + "(", open_count + 1, close_count)

        if close_count < open_count:
            backtrack(current + ")", open_count, close_count + 1)

    backtrack("", 0, 0)
    return result

Let's walk through the key decisions in this code.

The function starts with an empty string and both counters at zero. At each recursive call, it checks whether it can add "(" (open count still below n) and whether it can add ")" (close count still below open count). When both options are available, it explores both branches, depth-first.

The base case fires when the current string reaches length 2 * n. At that point, open and close must both equal n (the constraints enforce this), so the string is guaranteed to be valid. We append it directly, no need to copy, because string concatenation in Python creates a new string each time.

Notice there is no explicit "unchoose" step. Because we pass current + "(" as a new string rather than mutating a list, each recursive call gets its own copy. The backtracking is implicit in the call stack. This is a common pattern for string-building problems.

Visual walkthrough

Let's trace the algorithm for n = 2. There are only two valid results, "(())" and "()()", but the recursion explores several paths to find them. Watch how the pruning rules prevent invalid branches.

The key moment is at the root: with open = 0 and close = 0, you cannot add ")" because close is not less than open. That single rule eliminates half the tree immediately. At every level, the constraints trim branches that would lead to malformed strings, keeping the search space small.

Complexity analysis

Time: The number of valid parentheses strings for n pairs is the nth Catalan number, C(n) = (2n)! / ((n+1)! * n!), which grows as O(4^n / sqrt(n)). Each valid string takes O(n) to construct, so the total work is O(n * 4^n / sqrt(n)). The pruning ensures we do not explore more states than necessary.

Space: The recursion depth is 2n (one level for each character in the output string), so the call stack uses O(n) space. The output itself stores all Catalan-number results, each of length 2n.

Edge cases

Before submitting, verify these:

• n = 0: Should return [""] or [] depending on the problem statement. LeetCode expects [] for n=0, but some versions return a list with the empty string. Read the constraints carefully.
• n = 1: Should return ["()"]. Only one valid combination.
• Large n: n=8 produces 1430 valid strings. The algorithm handles this without issue because pruning keeps the tree manageable.

The building blocks

This problem is built on one core reusable pattern that CodeBricks drills independently.

Constrained backtracking

The general template for constrained backtracking looks like this:

def backtrack(state):
    if is_complete(state):
        record(state)
        return

    for choice in valid_choices(state):
        apply(choice)
        backtrack(state)
        undo(choice)

In generate parentheses, valid_choices is determined by the two counting rules. apply is appending a character. undo is handled implicitly by string immutability. The pattern is the same skeleton you see in Combination Sum, N-Queens, and Word Search. The only thing that changes is how you define "valid choices" and "is complete."

The constrained backtracking pattern shows up whenever:

• You are building a result incrementally (character by character, row by row, cell by cell)
• At each step, only some choices are valid based on the current state
• You need all valid results, not just one or a count

Problems using this same pattern include Letter Combinations of a Phone Number (LeetCode 17), Sudoku Solver (LeetCode 37), and Palindrome Partitioning (LeetCode 131).

Common mistakes

1. Allowing close to exceed open. If you add ")" without checking close < open, you generate invalid strings like ")(", ")(", or "())(". The close-less-than-open rule is the critical guard.

2. Using a mutable list and forgetting to copy. If you build the result with a list (current.append("(")) instead of string concatenation, you need to explicitly pop after the recursive call. If you forget, the state leaks between branches. String concatenation avoids this because it is immutable.

3. Checking length instead of counters for the base case. Some people check if open == n and close == n instead of if len(current) == 2 * n. Both work, but checking length is simpler. The constraints already guarantee that when length equals 2n, both counters equal n.

4. Not pruning early enough. If you build the full string first and then validate it, you generate 2^(2n) candidates instead of the Catalan number of valid ones. The whole point of backtracking is to prune during construction, not after.

From understanding to recall

You see the recursion tree. You understand the two pruning rules: add "(" when open is below n, add ")" when close is below open. But can you write this solution from scratch in under two minutes without looking anything up?

That is the gap between understanding and interview readiness. Under pressure, people forget which counter to compare, mix up the base case, or accidentally allow invalid branches. These are not conceptual problems. They are recall problems.

Spaced repetition closes that gap. You write the constrained backtracking template from memory at increasing intervals. After a few rounds, the two rules and the recursive structure are automatic. You see "generate parentheses LeetCode" and the code flows out without hesitation.

The constrained backtracking pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Valid Parentheses - Uses a stack to check whether a given string of parentheses is valid. Generate Parentheses builds valid strings from scratch. Valid Parentheses validates existing ones. Together they cover both directions of the parentheses problem family.
• Combination Sum - Another backtracking problem with pruning, but uses a loop over candidates instead of two fixed choices. Compare the pruning strategies: Combination Sum prunes when a candidate exceeds the remaining target, while Generate Parentheses prunes when a counter violates the open/close invariant.

CodeBricks breaks Generate Parentheses into its constrained backtracking building block, then drills it independently with spaced repetition. You type the two pruning rules and the recursive skeleton from scratch until they are automatic. When a backtracking problem shows up in your interview, you do not think about it. You just write it.