022. Generate Parentheses

Quick Identifier

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

Quick Sights

Time Complexity: O(4^n / sqrt(n)) from the optimal approach.
Space Complexity: See optimal approach. from the optimal approach.
Core Mechanism: Given pairCount, return all strings of pairCount pairs of well-formed parentheses — each string length 2 * pairCount.

Concept Explanation

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

The key is to state the invariant before coding: what part of the input is already settled, what state is still unresolved, and what single operation makes progress without losing correctness.

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

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

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;
}