Generate Parentheses

Medium· backtracking· pruning

Problem

Given n pairs of parentheses, produce every string of length 2n that is correctly balanced. The result can be in any order.

Examples

Input: n = 3

Output: ["((()))","(()())","(())()","()(())","()()()"]

Input: n = 1

Output: ["()"]

Constraints

• 1 <= n <= 8

Hints & approach

Hint 1

Generating every string of ( and ) and filtering is wasteful. Prune as you build.

Hint 2

Track how many opens and closes you have placed so far.

Hint 3

You may add "(" while opens < n, and ")" only while closes < opens.

Approachtry the hints first

Backtrack with counts of open and close brackets placed. Adding "(" is allowed while open < n; adding ")" is allowed only while close < open, which guarantees the prefix never becomes invalid. When the string reaches length 2n it is balanced by construction, so record it. Because no branch ever dead-ends, the work is proportional to the output, which is the nth Catalan number of strings.

Time O(4^n / sqrt(n)) · Space O(n) recursion, excluding output

← PreviousLetter Combinations of a Phone Number Next →Palindrome Partitioning