The problem
Given n, list every valid arrangement of n pairs of parentheses.
Input: n = 3 Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]
Picture it
Think of stacking cups: “(” opens a cup and “)” closes one. We build the string one character at a time, exploring a decision tree. We may add “(” while we still have openers left, and add “)” only if there is an open cup to close. Every path that uses all n pairs is a valid answer.
How to recognise it
- The task says list every arrangement, not count them or find one. Listing everything usually means backtracking: build an answer one choice at a time and undo the choice to try the next.
- Each step has a tiny set of choices (here only
(or)). - A partial answer can already be ruled out ("more closers than openers so far"), so you can stop exploring a branch early instead of finishing it and throwing it away.
- n is at most 8. Small limits like this are a hint that the output itself is exponential in size.
Start with brute force
Generate every string of length 2n made of ( and ), then keep the ones that are balanced. A string is balanced if a running depth never drops below zero and ends at zero.
from itertools import product
def balanced(s):
depth = 0
for ch in s:
depth += 1 if ch == "(" else -1
if depth < 0:
return False
return depth == 0
def generate_brute(n):
return ["".join(p) for p in product("()", repeat=2 * n)
if balanced("".join(p))]
There are 2^(2n) = 4^n strings, each checked in O(n), so time is O(n · 4^n). For n = 8 that is 65,536 strings, which still runs quickly, but only 1,430 of them (about 2%) are valid. Every extra pair multiplies the work by 4, and almost all of it is thrown away.
From brute force to the idea
- Find the waste. Any string starting with
)is doomed, yet the brute force builds all 2^(2n − 1) of them before rejecting each one. - Check while building. Build the string one character at a time and keep two counts:
openedandclosed. - Two rules decide every choice. You may add
(whileopened < n, because only n are available. You may add)only whileclosed < opened, because a closer needs an unmatched opener before it. - Every finished string is valid. These rules keep every prefix legal and use exactly n of each, so when
len(s) == 2 * nthe string goes straight intooutwith no final check. - Order comes for free. The code tries
(before), and(sorts before), so the output is in sorted order.
This is the key idea: prune with the two counts so that every branch you explore ends in a valid answer.
The key idea
Backtracking with two counts (open used, close used). Only add “)” when close < open, so every result is valid by construction.
Python solution
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 outIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
The number of valid strings is the n-th Catalan number, C(n) = (2n choose n) / (n + 1), which grows like 4^n / n^1.5 (C(8) = 1,430).
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n · 4^n): every string of length 2n, each checked in O(n) | O(n · C(n)) for the output, plus O(n) for one candidate |
| Pruned backtracking (shown code) | O(n · C(n)), about O(4^n / √n): every branch leads to an answer and each string costs O(n) to build | O(n · C(n)) for the output; the recursion is 2n calls deep |
Edge cases
- n = 1: returns
["()"]. - n = 3: returns the five strings in the example, in the same sorted order.
- n = 0: returns
[""], one empty arrangement. LeetCode starts at n = 1. - n = 8: 1,430 strings, recursion depth 17 calls, far below Python's default limit of 1,000.
- Building strings with
s + "("copies the prefix each time. That is fine at this size; a shared list withappendandpopavoids the copies.
Common mistakes
- Allowing
)wheneverclosed < ninstead ofclosed < opened. That produces strings like")(". - Allowing
(whileopened <= n, which uses one opener too many. - Using a shared list for the current string but forgetting to
popafter the recursive call returns, so later answers contain leftovers. - Generating with a set to remove duplicates. The two rules never produce the same string twice, so the set only hides a bug.
List every valid arrangement of n pairs whose nesting depth is at most d. For n = 3 and d = 2 that removes "((()))", leaving four strings. Describe your approach, then write it if you like.
Compare with our answer
The depth at any moment is opened - closed. Add a third rule: only add ( if it would not push the depth past d. The rest is unchanged.
def generate_depth(n, d):
out = []
def build(s, opened, closed):
if len(s) == 2 * n:
out.append(s)
return
if opened < n and opened - closed < d:
build(s + "(", opened + 1, closed)
if closed < opened:
build(s + ")", opened, closed + 1)
build("", 0, 0)
return out
generate_depth(3, 2) gives ["(()())", "(())()", "()(())", "()()()"]. With d = 1 the only answer is "()" * n.
A strong answer mentions: that opened - closed is the current depth, that the extra check goes on the ( branch only, and that every explored branch still ends in an answer.
1. You must list every order of n pushes and n pops that never pops an empty stack. Which approach fits best?
Push and pop map exactly to ( and ), so the same two counting rules prune every bad branch. Generate-and-filter works but explores 4^n orders, and a formula gives the count, not the list.
2. Why does the shown code not check that a finished string is balanced?
closed < opened stops any prefix from having more closers, and opened < n with a length of 2n forces exactly n of each. Even length alone is not enough: ")(" has even length.
3. A learner changes if closed < opened: to if closed < n:. What does generate(1) return now?
A closer is now allowed before any opener, so ")(" is built and appended. The length check still requires 2n characters, and "((" would need the ( rule to be loosened instead.
Score 60% or more and the lesson is marked complete.