Generate Parentheses Combinations

Given an integer \( n \), generate all combinations of \( n \) pairs of valid parentheses. A combination is valid if every opening bracket has a corresponding closing bracket and the pairs are properly nested. The output must be in lexicographical order.

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

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

This is a classical backtracking problem that requires exploring all potential solutions while maintaining the validity of the parentheses sequence.

inputFormat

The input consists of a single integer \( n \) provided via standard input (stdin) that represents the number of pairs of parentheses.

outputFormat

Output all the valid combinations of parentheses in lexicographical order via standard output (stdout). Each combination should be printed on a new line.

## sample

1

()

</p>