Recursion and Backtracking Generating every choice

324. Generate Parentheses

Given an integer n, return every balanced string made of n opening brackets ( and n closing brackets ). Each string is 2n characters long.

A string of round brackets is balanced when its brackets can be split into pairs, where each pair is a ( followed later by a ). Two pairs may sit side by side, as in ()(), or one may sit entirely inside the other, as in (()), but they may not overlap. So (()()) is balanced, and ())(() is not: its third character is a ), and the only ( before it is already taken by the second character. Valid Parentheses checks one string this way.

Return each balanced string exactly once. The strings can come back in any order. The examples list them in sorted order, where ( comes before ).

Example 1

Input: n = 3

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

Explanation: Five strings of three pairs are balanced. In ((())) all three pairs are nested, in ()()() all three sit side by side, and the other three strings mix the two.

Example 2

Input: n = 1

Output: ["()"]

Explanation: One pair gives only one string. )( holds the same two brackets, but its ) comes first, with no ( before it to pair with.

Example 3

Input: n = 5

Output:

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

Explanation: There are 42 balanced strings of five pairs. The count grows fast: it is 1, 2, 5, 14 and 42 for n = 1 to 5, and 16,796 for n = 10.

Check your understanding

Work out the answer for this input before you write any code.

n = 2

Constraints

1 ≤ n ≤ 10

Clarifying questions

What you would ask an interviewer before writing any code.