The problem
Given n pairs of parentheses, return every string of n opening and n closing parentheses that is well-formed — every ) closes an earlier (.
Examples
01
- Input
n = 3
- Output
["((()))", "(()())", "(())()", "()(())", "()()()"]
02
- Input
n = 1
- Output
["()"]
Constraints
- 1 ≤ n ≤ 8
The idea
Build the string one character at a time, and only ever add a character that keeps it valid. An ( may be added while fewer than n have been used. A ) may be added only while there are more ( than ) so far — otherwise it would close nothing.
Trying both choices at each step, and undoing each after exploring it, is backtracking. Because an invalid prefix is never started, every finished string of length 2n is well-formed, and none is produced twice.
- Time
- O(4ⁿ / √n) — proportional to the number of answers (the Catalan number) times their length
- Space
- O(n) — the recursion and the string being built
Solution · every language run against every case
class Solution: def generateParenthesis(self, n: int) -> List[str]: out, path = [], [] def build(opened: int, closed: int) -> None: if len(path) == 2 * n: out.append("".join(path)) return if opened < n: # an opener is allowed while any remain path.append("(") build(opened + 1, closed) path.pop() if closed < opened: # a closer is allowed only if it has an opener to match path.append(")") build(opened, closed + 1) path.pop() build(0, 0) return out