Generate Parentheses

Back to problems

Leetcode

Medium

Backtracking

Recursion

Strings

Combinatorics

Google

Generate Parentheses

Generate all combinations of well-formed parentheses strings of length $2n$ .

Acceptance 0%

Start Practice

Problem Statement

Given an integer n, generate every distinct string that contains exactly n left parentheses ( and n right parentheses ) and is a valid well-formed parentheses sequence.

A parentheses string is valid if:

Every prefix has at least as many ( as ).
The total number of ( equals the total number of ).

Return all valid combinations in any order.

Input Format

A single integer n.

Output Format

Return a list of strings, where each string is a valid parentheses sequence using exactly n pairs.

Constraints

$1 \le n$ is typically small enough for exhaustive generation.
The number of valid results grows combinatorially with n.

Hints

Build the string one character at a time.
Never add a right parenthesis unless there are more unmatched left parentheses available.
Stop when the current string reaches length $2n$ .

Input Format

An integer n representing the number of pairs of parentheses.

Output Format

A list of all valid well-formed parentheses strings containing exactly n pairs.

Constraints

Generate only valid sequences.
Use exactly n opening and n closing parentheses.
Result order does not matter.

Examples

Sample cases returned by the problem API.

Example 1

Input

n = 3

Output

["((()))","(()())","(())()","()(())","()()()"]

Explanation

There are five valid sequences using exactly three pairs of parentheses.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress