Practice: Generate Parentheses
Backtracking with rules.
Write every valid way to arrange three pairs of brackets. Valid means every opening bracket gets closed, in the right order. Pause. When is it allowed to add an opening bracket, and when a closing one?

- Three pairs of brackets
- Every valid arrangement
- When can we add each kind?
Two simple rules
We build the string one bracket at a time. We may add an opening bracket if we haven't used all of them. We may add a closing bracket only if there are more opens than closes so far. When the string is full, it's valid, so we keep it. Run it. Five arrangements.
def generate(n):
out = []
def build(s, opened, closed):
if len(s) == 2 * n:
out.append(s)
return
if opened < n:
build(s + "(", opened + 1, closed)
if closed < opened:
build(s + ")", opened, closed + 1)
build("", 0, 0)
return out
print(generate(3))['((()))', '(()())', '(())()', '()(())', '()()()']
Pruning makes it fast
Without the rules, we'd build all sixty four strings of six brackets, and check each one. The rules stop bad strings as soon as they start, so we only ever build valid ones. That's the heart of good backtracking. Prune early.
| key | value |
|---|---|
| Open | if opened < n |
| Close | if closed < opened |
| Full | keep it |
| Key | prune early |
Summary
Generate parentheses with backtracking, using two rules that only allow valid strings. Next, finding cycles in a graph.
Key takeaways- Add open if any left
- Close only if open
- Prune early