Generate Parentheses Backtracking DSA Solution

Learning Outcome

After this lesson, you should be able to prune invalid prefixes before they are generated.

Problem Statement

Given n pairs of parentheses, generate all combinations of well-formed parentheses.

Input	Output	Why
`n = 3`	`["((()))","(()())","(())()","()(())","()()()"]`	Only strings where every prefix has close count <= open count are valid.

Brute Force Approach

Generate every string of length 2n made of ( and ), then filter invalid strings. This creates many impossible states.

Optimized Approach

Backtrack only through valid states: add ( while open < n, and add ) only while close < open.

Exact Pseudocode

answer = []
dfs(path, open, close):
  if length(path) == 2 * n:
    answer.add(path)
    return
  if open < n:
    dfs(path + "(", open + 1, close)
  if close < open:
    dfs(path + ")", open, close + 1)
return answer

Reference Code

class Solution:
    def generateParenthesis(self, n):
        answer = []

        def dfs(path, open_count, close_count):
            if len(path) == 2 * n:
                answer.append(path)
                return

            if open_count < n:
                dfs(path + "(", open_count + 1, close_count)
            if close_count < open_count:
                dfs(path + ")", open_count, close_count + 1)

        dfs("", 0, 0)
        return answer

Sample Dry Run

Step	State	Result
Start	path="", open=0, close=0	Only "(" is allowed
path="("	open=1, close=0	Can add "(" or ")"
Invalid prefix blocked	close can never exceed open	No path starts with ")"
Length 6	Valid path copied	Answer receives one string

Complexity

Measure	Value	Reason
Time	O(Cn)	The number of valid strings is the nth Catalan number.
Space	O(n)	The recursion path length is at most 2n.

Edge Cases

n = 1 returns ["()"].
Never allow close count to exceed open count.
Stop when path length reaches 2n.

Interview Checklist

Track open and close counts separately.
Prune invalid prefixes early.
Add a complete path only at length 2n.

FAQs

Why is close < open required?

A closing parenthesis is valid only if there is an unmatched opening parenthesis.

Why not generate all strings first?

Most generated strings would be invalid, so pruning saves work and is clearer.

What is the core pattern?

Valid-state backtracking.

Generate Parentheses: Valid State Backtracking Pattern