Generate Parentheses

---

Intuition

• If you open a parentheses, you have to close it afterward.
• On each step of the recursive tree, you have three possibilities
  • You have no parentheses left to close, and none left to open. Just append to result.
  • You have more parentheses left to open. Open it.
  • You have more parentheses left to close. Close it.
• The last two points can happen together (i.e. you can have no parentheses left to open, but still need to close out some).

Complexity

Runtime

• N opening and closing parentheses per call ($2N$)
• At each step, you either open or close ($2^{2N}$) = $4^N$
• In practice, it is the Catalan number - Wikipedia

Space

• $O(N\ast 4^N)$
  • There are $4^N$ strings generated
  • N strings are stored

Code

Backtracking without Outer List

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def r(n, cur, op):
            res = []
            if n == 0 and op == 0:
                res.append(cur)
            if n > 0:
                res.extend(r(n - 1, cur + "(", op + 1))
            if op > 0:
                res.extend(r(n, cur + ")", op - 1))
 
            return res
 
        return r(n, "", 0)

Backtracking

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        def r(n, cur, op):
            if n == 0 and op == 0:
                res.append(cur)
                return
            if n > 0:
                r(n - 1, cur + "(", op + 1)
            if op > 0:
                r(n, cur + ")", op - 1)
 
        r(n, "", 0)
        return res

Notes

Notebook

Cards

START Basic Front: Generate Parentheses Back: On each recursive step, you have no parentheses left to open or close, or you have some left to open or close. END

---

References

• Generate Parentheses
• Debugging generate parentheses recursion | Claude