Generate Parentheses
Generate Parentheses is a classic backtracking problem where the goal is to generate all possible combinations of well-formed parentheses for a given number n. The algorithm builds the string step by step and ensures validity by never allowing the number of closing parentheses to exceed the number of opening ones. This constraint prunes invalid branches early and makes the search efficient.
Generate Parentheses Visualization
Standby
Current State
∅
open: 0close: 0len: 0/6
DFS Probe Arm
press Run or Start to begin
Valid Results (0)
— no valid combinations yet —
DFS Code Sync
1dfs(str, open, close)
2if (str.length === 6) result.push(str)
3if (open < 3) dfs(str + "(", open + 1, close)
4if (close < open) dfs(str + ")", open, close + 1)
5current = ""
Legend
Active DFS node
Valid combination
Visited state
Active recursion edge
0 steps · 0 found
Execution Speed5x
SlowFast
Stack Pressure0%
Deep recursion visual pressure meter
Complexity
Time Complexity:
O(4^n / sqrt(n))Space Complexity:
O(n)Pseudocode
function generateParentheses(n):
result = []
backtrack('', 0, 0)
function backtrack(current, open, close):
if length(current) == 2 * n:
add current to result
return
if open < n:
backtrack(current + '(', open + 1, close)
if close < open:
backtrack(current + ')', open, close + 1)
return result