philosyang.com

22. Generate Parentheses: Backtracking

ref: https://neetcode.io/solutions/generate-parentheses

general idea

  1. we can add ( only if opened_n < n
  2. we can add ) only if closed_n < closed_n
  3. output is valid iff opened_n == closed_n == n
 1class Solution:
 2    def generateParenthesis(self, n: int) -> List[str]:
 3        stack = []
 4        result = []
 5
 6        def bt(opened_n, closed_n):
 7            if opened_n == closed_n == n:
 8                result.append("".join(stack))
 9                return
10
11            if opened_n < n:
12                stack.append("(")
13                bt(opened_n + 1, closed_n)
14                stack.pop()
15
16            if closed_n < opened_n:
17                stack.append(")")
18                bt(opened_n, closed_n + 1)
19                stack.pop()
20
21        bt(0, 0)
22
23        return result

I need a write on mastering backtracking.

Addendum (2025-08-02):

I tried to tackle this again after a week - I stumbled a bit, but this new solution is clean, too.

 1class Solution:
 2    def generateParenthesis(self, n: int) -> List[str]:
 3        result = []
 4
 5        def bt(opened, closed, t):
 6            # 1. if max reached, combine then result
 7            # 2. if we can still open
 8            # 3. if we can still close
 9            if opened == closed == n:
10                result.append("".join(t))
11                return
12
13            if opened < n:
14                t.append("(")
15                bt(opened + 1, closed, t)
16                t.pop()
17
18            if closed < opened:
19                t.append(")")
20                bt(opened, closed + 1, t)
21                t.pop()
22
23        bt(0, 0, [])
24
25        return result

#Neetcode150 #Backtracking #Python