How do you approach Generate Parentheses?

Use backtracking - at each step you can add '(' or ')'.

What is the time complexity of Generate Parentheses?

Time complexity: O(4^n / sqrt(n)) - the nth Catalan number. Space complexity: O(n) for the recursion stack.

What are common mistakes on Generate Parentheses?

Pushing the working array into the results without copying it, so every entry aliases the same array. Forgetting to undo the choice after the recursive call returns. Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.

gitGood.dev

← Back to problems

Generate Parentheses

MediumAlgorithms

Description

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

Generate Parentheses: approach, complexity and pitfalls

A medium backtracking problem, graded against 5 test cases (2 of them hidden).

The pattern: Backtracking

Systematic exploration of all candidates, abandoning partial ones that cannot work.

Reach for it when you see: "All permutations/combinations/subsets", or constraint puzzles like N-Queens and Sudoku.

If you are stuck

Show the 3-step hint ladder

Use backtracking - at each step you can add '(' or ')'.
You can add '(' only if you haven't used all n opening parentheses.
You can add ')' only if the count of ')' is less than the count of '(' so far.

The optimal approach

Show the approach: Backtracking

Track the count of open and close parentheses used. At each step, add '(' if open count < n, and add ')' if close count < open count. When the string length reaches 2n, add to results.

Time: O(4^n / sqrt(n)) - the nth Catalan number
Space: O(n) for the recursion stack

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Backtracking mistakes

These apply to the pattern as a whole, not just this problem.

Pushing the working array into the results without copying it, so every entry aliases the same array.
Forgetting to undo the choice after the recursive call returns.
Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.