Generate Parentheses

mediumStack & Queue+20 XPTime limit 2s

Print every well-formed string of n pairs of parentheses.

Input: one integer n.

Output: all valid strings, one per line, in alphabetical order (where ( comes before )).

Constraints: 1 ≤ n ≤ 10.

Think about it: backtracking — build the string one character at a time. You may add ( while fewer than n have been opened, and ) while it would not close more than were opened. If you always try ( first, the strings come out already sorted.

Sample input 1

Sample output 1

((()))
(()())
(())()
()(())
()()()

Sample input 2

Sample output 2

()

📖 Stuck? Learn the pattern

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…