022. Generate Parentheses

At a Glance

Topic: stack
Pattern: DFS / Backtracking
Difficulty: Medium
Companies: Amazon, Google, Meta, Bloomberg, Apple
Frequency: Very High
LeetCode: 22

Problem (one-liner)

Given pairCount, return all strings of pairCount pairs of well-formed parentheses — each string length 2 * pairCount.

Recognition Cues

Enumerate all Catalan-valid bracket strings
Remaining opens possible vs remaining closes must stay ≥ 0
Recursion with (openUsed, closeUsed) state or explicit stack simulation

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — generate all 2^(2n) strings, filter — exponential overhead.
Better — backtrack adding ( if openUsed < pairCount, ) if closeUsed < openUsed.
Optimal — same backtracking — O(4^n / sqrt(n)) output size bound (Catalan many paths).

Optimal Solution

Go

func generateParenthesis(pairCount int) []string {
	out := []string{}
	var build func(prefix string, openUsed int, closeUsed int)
	build = func(prefix string, openUsed int, closeUsed int) {
		if len(prefix) == 2*pairCount {
			out = append(out, prefix)
			return
		}
		if openUsed < pairCount {
			build(prefix+"(", openUsed+1, closeUsed)
		}
		if closeUsed < openUsed {
			build(prefix+")", openUsed, closeUsed+1)
		}
	}
	build("", 0, 0)
	return out
}

JavaScript

function generateParenthesis(pairCount) {
	const results = [];
	function build(prefix, openUsed, closeUsed) {
		if (prefix.length === 2 * pairCount) {
			results.push(prefix);
			return;
		}
		if (openUsed < pairCount) {
			build(prefix + '(', openUsed + 1, closeUsed);
		}
		if (closeUsed < openUsed) {
			build(prefix + ')', openUsed, closeUsed + 1);
		}
	}
	build('', 0, 0);
	return results;
}