Generate Parentheses

Generate Parentheses is the classic introduction to backtracking. It teaches you to build candidates one choice at a time and to prune any choice that can never lead to a valid answer — so you only ever walk down promising branches.

The slow way first

The brute-force idea: generate every string of length 2n made of ( and ) — there are 2^(2n) of them — then keep only the balanced ones. That works, but it explores a huge number of dead strings like ))(( that were doomed from the first bracket.

The question to ask: can I avoid ever building a string that cannot be completed? Yes — if I only add a bracket when it keeps the string still completable, I never waste time on garbage.

The idea: only make legal moves

Grow the string one bracket at a time while tracking two counts: open (how many ( used) and close (how many ) used). Two rules keep every partial string valid:

• Add ( only while open < n — we still have open brackets to spend.
• Add ) only while close < open — there is an unmatched ( to close.

When the string reaches length 2n, it is guaranteed balanced, so we record it. These choices form a decision tree, and we walk it with recursion, backtracking whenever a branch finishes.

The two guard conditions are the pruning: they cut off every branch that could never balance, so the tree we actually explore is small.

Walk through it

Step through the animation for n = 2. We dive down the left spine adding ( twice, then ) twice to reach the valid leaf "(())", and record it. Then the recursion backtracks up to "(" and takes the other choice, building "()(" and finally "()()". Two leaves, two answers.

Pseudocode

result = empty list
backtrack(cur, open, close):
    if length of cur == 2n:
        add cur to result          # balanced by construction
        return
    if open < n:                   # legal to add "("
        backtrack(cur + "(", open + 1, close)
    if close < open:               # legal to add ")"
        backtrack(cur + ")", open, close + 1)
start with backtrack("", 0, 0)
return result

The Python solution

def generate_parenthesis(n):
    result = []
 
    def backtrack(cur, open, close):
        if len(cur) == 2 * n:
            result.append(cur)
            return
        if open < n:
            backtrack(cur + "(", open + 1, close)
        if close < open:
            backtrack(cur + ")", open, close + 1)
 
    backtrack("", 0, 0)
    return result

• cur is the string built so far; open and close count the brackets used.
• The base case len(cur) == 2 * n means the string is complete — and because every move was legal, it is balanced, so we save it.
• if open < n is the add-open branch: spend one of our n opening brackets.
• if close < open is the add-close branch: only allowed when an unmatched ( exists, which is what keeps the string valid.
• When both if checks finish, the call returns and the recursion backtracks to try the sibling choice.

Complexity

The number of valid combinations is the nth Catalan number, and pruning means we touch close to that many nodes rather than all 2^(2n) strings. The space is O(n) for the recursion depth (the string length never exceeds 2n).

When this pattern shows up

Practice