Generate Parentheses

Medium

Open while you can, close while it stays valid

Problem

Generate all combinations of n pairs of well-formed parentheses.

In simple words

Add '(' while you have some left, add ')' only when it can close an earlier '(' — always balanced.

The idea

Track how many brackets of each kind you have placed. You may open while opens are below n, and you may close only while closes are strictly below opens — that second rule is what guarantees every generated string is well-formed.

The trick

Never close more than you have opened; that single check replaces any validity test at the end.
A string is complete when both counts reach n.
The count of results is the nth Catalan number.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

←→stepspaceplay

1/2

Optimal

timeO(4^n/sqrt n)spaceO(n)

1f(open,close,cur):2  if len(cur)==2n: output; return3  if open<n: f(open+1,close,cur+'(')4  if close<open: f(open,close+1,cur+')')

Input

array: [3]

Output

answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: n = 3
Output:: ['((()))', '(()())', '(())()', '()(())', '()()()']
Explanation:: All 5 balanced arrangements of 3 pairs.

Example 2

Input:: n = 1
Output:: ['()']
Explanation:: Only ().

Example 3

Input:: n = 2
Output:: ['(())', '()()']
Explanation:: (()) and ()().

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.