LeetCode #22: Generate Parentheses — Solved in Java

Backtracking and Catalan DP by composition

Image Source

The Generate Parentheses problem is about producing every balanced combination of parentheses for a given number of pairs. The goal is to cover the entire set of valid strings without drifting into invalid ones where a close parenthesis arrives before its match. It’s less about testing a single string and more about constructing the full collection in a way that respects the rules of balance at every step.

Solving this well comes down to how you frame the problem in your head. Brute force can feel tempting, but that creates far too many dead ends. A stronger mindset is to focus only on paths that remain valid as they grow, or to think in terms of smaller valid results being combined to make larger ones. With that perspective, two main strategies emerge. One grows strings character by character while pruning invalid branches through backtracking. The other leans on the Catalan recurrence, where each balanced string is built from smaller blocks stored in a dynamic table. Both produce the full answer set, but they guide you toward different ways of reasoning about structure and reuse.

LeetCode: Generate Parentheses

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

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Constraints:

• 1 <= n <= 8

Solution 1: Simple Backtracking

This method grows well-formed strings one character at a time. An open parenthesis gets added while there’s quota left. A close parenthesis gets added only when it keeps the prefix valid. A single StringBuilder holds the path and gets trimmed as recursion unwinds.