0022. Generate Parentheses

Interactive visualization of parentheses generation algorithms

Backtracking
DP (Catalan Build)
Speed: 5
Backtracking: Build strings character by character. Add ( if open < n, add ) if close < open. When length reaches 2n, we found a valid combination. Time: O(4^n / sqrt(n))
Step: 0
Current: empty
Found combinations: 0
Click "Step" or "Play" to begin...
Waiting to start...
DP (Catalan Build): Build from subproblems. Every valid string of i pairs = "(" + dp[j] + ")" + dp[i-1-j]" for all j from 0 to i-1. Time: O(4^n / sqrt(n))
Step: 0
dp[i] = { "(" + left + ")" + right | left in dp[j], right in dp[i-1-j] }
Click "Step" or "Play" to begin...
Waiting to start...