⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#22) before relying on it.

Generate Parentheses

An interactive visualization of DFS/backtracking to generate all valid parentheses combinations. Watch the decision tree build as the algorithm chooses to add '(' or ')' at each step.

DFS LeetCode 22 ↗ Medium

The Problem

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

For example, given n = 3, the result is:
["((()))", "(()())", "(())()", "()(())", "()()()"]

Interactive Visualization

n (pairs)

Preset

Speed:

Decision Tree

Open: 0 / 3

Close: 0 / 3

Results found: 0

No combinations found yet.

Code

fun generateParenthesis(n: Int): List<String> {    val result = mutableListOf<String>()    fun dfs(openCount: Int, closeCount: Int, current: String) {        if (current.length == 2 * n) {            result.add(current)            return        }        if (openCount < n) {            dfs(openCount + 1, closeCount,                current + "(")        }        if (closeCount < openCount) {            dfs(openCount, closeCount + 1,                current + ")")        }    }    dfs(0, 0, "")    return result}

def generateParenthesis(n):    result = []    def dfs(open_count, close_count, current):        if len(current) == 2 * n:            result.append(current)            return        if open_count < n:            dfs(open_count + 1, close_count,                current + '(')        if close_count < open_count:            dfs(open_count, close_count + 1,                current + ')')    dfs(0, 0, '')    return result

Status & Log

Press Step or Play to begin.

How It Works

Key Insight

At each position, we can add ( if open_count < n, or ) if close_count < open_count. This ensures we never have more closing than opening parentheses at any point in the string, which is exactly the condition for well-formed parentheses.

The Algorithm

DFS with two choices at each step: add an opening paren ( or a closing paren ).
Pruning rule 1: only add ( if we haven't used all n opening parens yet (open_count < n).
Pruning rule 2: only add ) if doing so won't create an invalid prefix (close_count < open_count).
Base case: when the string reaches length 2n, it's a valid combination — add it to the result.
The DFS naturally backtracks after exploring each branch, building the complete set of valid combinations.

Complexity

Time O(4ⁿ / √n)

Space O(n)

The number of valid parentheses combinations is the n-th Catalan number, which is C(2n, n) / (n+1), bounded by O(4ⁿ / n^3/2). Each combination takes O(n) to construct, giving O(4ⁿ / √n) total work. The recursion depth (and thus space for the call stack) is O(n).