LeetCode 22 · Stack

Generate Parentheses, explained with a picture

Stacking cups that open and close.

MediumStack
▶ Watch it step by step

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

  1. Find the waste. Any string starting with ) is doomed, yet the brute force builds all 2^(2n − 1) of them before rejecting each one.
  2. Check while building. Build the string one character at a time and keep two counts: opened and closed.
  3. Two rules decide every choice. You may add ( while opened < n, because only n are available. You may add ) only while closed < opened, because a closer needs an unmatched opener before it.
  4. Every finished string is valid. These rules keep every prefix legal and use exactly n of each, so when len(s) == 2 * n the string goes straight into out with no final check.
  5. 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 out

In 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).

ApproachTimeSpace
Brute forceO(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 buildO(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 with append and pop avoids the copies.

Common mistakes

  • Allowing ) whenever closed < n instead of closed < opened. That produces strings like ")(".
  • Allowing ( while opened <= n, which uses one opener too many.
  • Using a shared list for the current string but forgetting to pop after 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.
Your turn: limit the nesting depth

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.

Check what stuck

1. You must list every order of n pushes and n pops that never pops an empty stack. Which approach fits best?

2. Why does the shown code not check that a finished string is balanced?

3. A learner changes if closed < opened: to if closed < n:. What does generate(1) return now?

Score 60% or more and the lesson is marked complete.