DSA AnimatorDSA animations
Generate Parentheses LC #22 Medium Backtracking · Constraints
Problem

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

Example 1
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Explanation: Catalan number C(3) = 5 valid combinations.
Example 2
Input: n = 1
Output: ["()"]
Constraints: 1 ≤ n ≤ 8
Try Examples
Custom:
Approach
Constraint-Guided Backtracking
Two choices at each step: add '(' if open<n, add ')' if close<open. Base: length==2n. These constraints ensure every generated string is valid — no post-filtering needed.
Building String
(empty)
Bracket Counters
open ( placed
0
max: n
close ) placed
0
max: open
Results 0 found
Recursion Tree
Step Logic
Press ▶ Play or Next Step to begin.
✅
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Track open and close counts separately
2
Add '(' if open < n  |  Add ')' if close < open (ensures valid nesting)
3
Base: length == 2n → valid combination found
4
Catalan number C(n) results total
Time
O(4^n/√n)
Space
O(n)
Why Backtracking Works

Two branching choices at each step: add '(' or ')'. Constraints open<n and close<open prune invalid paths, ensuring only valid parenthesizations are generated. No post-filtering needed — every leaf is valid. Result count equals Catalan number C(n).

How to solve Generate Parentheses

LeetCode 22 · Medium · Backtracking · Pattern: Backtracking with Counts

Why the obvious approach is slow

Generating all 2 to the 2n strings and checking each one is wasteful. We can build only valid strings.

The key idea

Track how many opening and closing brackets are used. You may add an opening bracket while open is less than n. You may add a closing bracket only while close is less than open.

Remember

Open while open is less than n, close while close is less than open. The rules prune every invalid string before it is built.

Run the animation above on your own input, or watch the 1:29 video explanation of Generate Parentheses with a dry run and Java code.

More Backtracking problems