← Back to DSA Animator
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
Variables
open
0
close
0
curr len
0
found
0
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).