← all entries
A-024● Day 242026.05.28mediumleetcode #22neetcode150

Generate Parentheses

#string#dynamic-programming#backtracking
↗ leetcode #22 · generate-parentheses
01

Problem

· problem
P.024

Generate Parentheses

↗ leetcode #22

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

constraints
  • · 1 ≤ n ≤ 8
// paraphrased summary — see source for full text
examples
example 1input → output
3
["((()))","(()())","(())()","()(())","()()()"]
example 2input → output
1
["()"]
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    What exactly does well-formed parentheses mean?
  • ☐
    Must the output be in a specific order or can it be any order?
  • ☐
    For n=3, how many total parenthesis characters are there?
  • ☐
    Is it a good approach to generate all 2^(2n) binary combinations then filter for valid ones?
  • ☐
    What must be the relationship between open and closed counts at any point?
  • ☐
    Can we place all n opening parentheses first, then add closing ones?
  • ☐
    How many valid combinations exist for a given n?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Initialize stack
○
stack = []
○
res = []
○
stack = set()
○
stack = {}
step 2· Initialize results list
○
res = []
○
res = set()
○
res = {}
step 3· Check base case│ nested
○
if openN == closedN == n:
○
if openN == n:
○
if openN + closedN == 2 * n:
○
if len(stack) == 2 * n:
step 4· Constraint: can add opening paren│ nested
○
if openN < n:
○
if openN <= n:
○
if closedN < openN:
○
if openN < closedN:
step 5· Constraint: can add closing paren│ nested
○
if closedN < openN:
○
if closedN <= openN:
○
if closedN < n:
○
if openN < n:
step 6· Initiate backtracking
○
backtrack(0, 0)
○
backtrack(1, 0)
○
backtrack(n, n)
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
class Solution:
2
    def generateParenthesis(self, n: int) -> List[str]:
3
        stack = []
4
        res = []
5
6
        def backtrack(openN, closedN):
7
            if openN == closedN == n:
8
                res.append("".join(stack))
9
                return
10
11
            if openN < n:
12
                stack.append("(")
13
                backtrack(openN + 1, closedN)
14
                stack.pop()
15
            if closedN < openN:
16
                stack.append(")")
17
                backtrack(openN, closedN + 1)
18
                stack.pop()
19
20
        backtrack(0, 0)
21
        return res
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
3
→
["((()))","(()())","(())()","()(())","()()()"]
case 2
1
→
["()"]
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.