Module 16 · Backtracking and Combinatorial Search

157. Generate Balanced Parentheses

Bridge · Download this solution · All solutions and shared helpers

Problem

Return all well-formed strings containing n pairs of parentheses, for n>=0. Try '(' before ')' at every decision, giving lexicographic output. A valid prefix never has more closing than opening parentheses. n=0 returns [''].

Examples

Example 1

balanced_parentheses(3)
=> ['((()))', '(()())', '(())()', '()(())', '()()()']

Only prefixes with recoverable balance are explored.

Example 2

balanced_parentheses(0)
=> ['']

The empty string is balanced.

Example 3

balanced_parentheses(1)
=> ['()']

A closing cannot be chosen first.

Reveal the worked solution and reasoning

Why this mechanism works

Generating all 2^(2n) strings and validating them wastes work on prefixes that can never recover. Keep opened and closed counts while constructing the answer. An opening is available until n have been placed; a closing is available only when it can match an unmatched opening. These local rules preserve the global balance requirement.

State and boundaries

path has opened openings and closed closings, with 0<=closed<=opened<=n.

Protocol

At length 2*n save the joined path.
If opened<n, append an opening, explore and undo.
If closed<opened, append a closing, explore and undo.

Visualization

opened=2, closed=1 -> '((' + ')' = '(()'
unmatched openings = 1
closing allowed; opening allowed only if opened<n

Python implementation

def balanced_parentheses(n):
    output, path = [], []
    def visit(opened, closed):
        if len(path) == 2 * n:
            output.append(''.join(path))
            return
        if opened < n:
            path.append('(')
            visit(opened + 1, closed)
            path.pop()
        if closed < opened:
            path.append(')')
            visit(opened, closed + 1)
            path.pop()
    visit(0, 0)
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

balanced_parentheses(3)

L2 balanced_parentheses: output, path = [], []
n=3; output=[]; path=[]

L4 visit: if len(path) == 2 * n:
opened=0; closed=0; n=3; output=[]; path=[]

L8 visit: path.append('(')
opened=0; closed=0; n=3; output=[]; path=['(']

L4 visit: if len(path) == 2 * n:
opened=1; closed=0; n=3; output=[]; path=['(']

L8 visit: path.append('(')
opened=1; closed=0; n=3; output=[]; path=['(', '(']

L4 visit: if len(path) == 2 * n:
opened=2; closed=0; n=3; output=[]; path=['(', '(']

L8 visit: path.append('(')
opened=2; closed=0; n=3; output=[]; path=['(', '(', '(']

L4 visit: if len(path) == 2 * n:
opened=3; closed=0; n=3; output=[]; path=['(', '(', '(']

... 80 intermediate state changes omitted ...

L14 visit: path.pop()
opened=1; closed=0; n=3; output=['((()))', '(()())', '(())()', '()(())', '()()()']; path=['(']

L9 visit: visit(opened + 1, closed)
opened=0; closed=0; n=3; output=['((()))', '(()())', '(())()', '()(())', '()()()']; path=['(']

L10 visit: path.pop()
opened=0; closed=0; n=3; output=['((()))', '(()())', '(())()', '()(())', '()()()']; path=[]

L15 balanced_parentheses: visit(0, 0)
n=3; output=['((()))', '(()())', '(())()', '()(())', '()()()']; path=[]

Result: ['((()))', '(()())', '(())()', '()(())', '()()()']. Only prefixes with recoverable balance are explored.

balanced_parentheses(0)

L2 balanced_parentheses: output, path = [], []
n=0; output=[]; path=[]

L4 visit: if len(path) == 2 * n:
opened=0; closed=0; n=0; output=[]; path=[]

L5 visit: output.append(''.join(path))
opened=0; closed=0; n=0; output=['']; path=[]

L15 balanced_parentheses: visit(0, 0)
n=0; output=['']; path=[]

Result: ['']. The empty string is balanced.

Why the solution is correct

The two guards preserve valid prefix balance and the opening limit. A completed length-2n prefix must have exactly n of each symbol. Every valid string obeys the guards at every position, so its unique choice route is explored. Each choice increases length toward 2n.

Time and space

O(n*C_n) time and output characters for the nth Catalan number C_n, with O(n) auxiliary path and stack. n=0 is constant.

Common mistakes

Allowing a closing whenever closed<n admits invalid prefixes. Checking balance only at the end loses the pruning benefit.

Reasoning card

State: path has opened openings and closed closings, with 0<=closed<=opened<=n.

Invariant: Every prefix obeys closes <= opens <= n.

Decision to rehearse: Add open when available; add close only when closes < opens.

Finish: If closed<opened, append a closing, explore and undo

Transfer exercise

Impose a maximum nesting depth h by adding one guard on opened-closed.