All problems

Generate Parentheses

Medium · backtracking

Given a number n, return every string made of exactly n opening brackets ( and n closing brackets ) that is balanced.

A string is balanced when every closing bracket matches an earlier opening bracket that is still open. In other words, reading from left to right, you never have more ) than ( so far, and at the end the two counts are equal.

Every balanced string must appear exactly once. The strings may be returned in any order. When n is 0, the only balanced string is the empty string, so return a list holding one empty string.

Examples

Example 1

Input: n = 1

Output: ["()"]

Of the two strings with one of each, "()" and ")(", only "()" is balanced.

Example 2

Input: n = 2

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

Other arrangements such as "())(" fail because a closing bracket comes before there is anything to close.

Example 3

Input: n = 3

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

Five strings in total.

Constraints