Generate Parentheses Combinations

Given a non-negative integer \( n \) representing the number of pairs of parentheses, generate all combinations of well-formed parentheses.

A parentheses string is well-formed if every opening bracket \( ( \) has a corresponding closing bracket \( ) \) and the pairs are properly nested.

For example, when \( n = 3 \), the valid combinations are:

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

Your task is to use a backtracking approach to generate and print each valid combination on a separate line. If \( n = 0 \), print an empty line.

inputFormat

The input consists of a single integer \( n \) provided via stdin.

\( 0 \leq n \leq 12 \) (for example).

outputFormat

Output all valid parentheses combinations, each combination on a new line, using stdout.

The order of the combinations should follow the natural order generated by the backtracking algorithm.

## sample

1

()

</p>