DSA Factory
Free lessonsBacktracking · Stage 0 · Build, check, undo · Step 3

Generate valid parentheses

Prune impossible branches by only adding closing brackets when open brackets outnumber them. About 9 minutes.

What makes parentheses valid?

Think of doors: every door you open must be closed later, and you cannot close a door that was never opened. So a bracket string is valid when two things hold.

First, reading left to right, there are never more closing brackets than opening ones so far. Second, at the end the totals are equal.

Never close early: only add a closing bracket if there is an unclosed opening one.
Limit the openers: only add an opening bracket while you have used fewer than n.
n = 2 · faded branches are pruned: never explored
""(((((((()(())()()(()()()))
open
1
close
0

At the start, ')' would close something that was never opened. Prune it. Only '(' is allowed.

Move 1 of 5

Pruning the search tree

You could build every string of opens and closes and throw away the bad ones afterwards, but that wastes time. Better to check the rules before each step. If a branch would break a rule, do not go down it at all.

Cutting off a doomed branch early is called pruning. It is like a driver who sees a road is closed and never turns into it. When the string reaches length 2n, it is guaranteed valid.

Pruning: cutting off dead-end branches before exploring them.
Full length: a string of length 2n built this way is always valid.
In code
res, curr = [], []
def go(opens, closes):
    if len(curr) == 2 * n:
        res.append("".join(curr))
        return
    if opens < n:
        curr.append("(")
        go(opens + 1, closes)
        curr.pop()
    if closes < opens:
        curr.append(")")
        go(opens, closes + 1)
        curr.pop()
go(0, 0)
return res
Quick check

If your current string is '(()' with n = 3, which brackets can you place next?

  1. AEither '(' or ')'
  2. BOnly '('
  3. COnly ')'
Show the answer

Either '(' or ')'. open count (2) is < 3, so '(' is allowed; close count (1) is < open count (2), so ')' is allowed.

Your problem

Generate valid parentheses

Given an integer n, generate all combinations of well-formed parentheses strings using exactly n pairs of parentheses.

Example
n = 3 → ["((()))", "(()())", "(())()", "()(())", "()()()"]

1 ≤ n ≤ 8

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.
Start coding