Generate Valid Parentheses

Given an integer n, generate all combinations of well-formed parentheses. A combination is considered valid if every opening parenthesis '(' has a corresponding closing parenthesis ')' and the pairs are properly nested. Note that each valid combination has exactly 2n characters.

For example, when n=3, one possible set of valid combinations is:

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

All combinations should be printed in lexicographical order with each combination on a separate line.

inputFormat

The input consists of a single integer n (1 ≤ n ≤ 10) which represents the number of pairs of parentheses.

outputFormat

Output all valid combinations of parentheses, one per line, in lexicographical order.

1

()