LeetCode: 22. Generate Parentheses

Summary

Generate all well-formed parentheses combinations for n pairs.

Approach

Backtracking.

Rule for well-formed parentheses:

The number of used closing parentheses must never exceed the number of used opening parentheses.

Example:

(): Good
): Bad
()(): Good
()): Bad

Function

Initialization:

open_used: 0
close_used: 0
tags: []
n: number of pairs
result: []

Recursive:

If close_used == n, join tags into a string, append it to result, and return.
If open_used < n, add '(', recurse with open_used + 1, then backtrack (pop).
If close_used < open_used, add ')', recurse with close_used + 1, then backtrack (pop).

This guarantees every generated string is valid.

Complexity

Time complexity: O(Cn * n), where Cn is the nth Catalan number (the number of valid combinations).
Space complexity: O(n) for the recursion stack and current tags path (excluding output).