Generate Parentheses

Given an integer \(n\), generate all combinations of \(n\) pairs of well-formed parentheses. A well-formed (or balanced) parentheses string is defined as follows:

• An empty string is balanced.
• If \(S\) is balanced, then \( (S) \) is balanced.
• If \(A\) and \(B\) are balanced, then their concatenation \(AB\) is balanced.

Your task is to output all possible balanced parentheses combinations sorted in the order they are generated using the standard backtracking technique. For example, when \(n=3\), the valid combinations are:

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

Note that when \(n=0\) the output should be a single blank line representing the empty string.

inputFormat

The input consists of a single integer \(n\) (\(0 \le n \le 12\)), which represents the number of pairs of parentheses.

outputFormat

Output all valid combinations of well-formed parentheses for the given \(n\). Each combination should be printed on a separate line in the order they are generated by the backtracking algorithm.

## sample

1

()

</p>