Generate Parentheses
An interactive, step-by-step visualisation of Generate Parentheses.
- Category
- Recursion
- Time complexity
- O(4ⁿ/√n)
- Space complexity
- O(n) stack
Pseudocode
gen(open, close, cur):
if open == close == n: emit cur
if open < n: gen(open+1, close, cur+"(")
if close < open: gen(open, close+1, cur+")")
Reference implementation
def gen(open, close, cur, n, out):
if open == close == n:
out.append(cur); return
if open < n:
gen(open+1, close, cur+'(', n, out)
if close < open:
gen(open, close+1, cur+')', n, out)