Balanced Parentheses Generation

Given an integer n, generate all distinct combinations of n pairs of balanced parentheses.

A combination is valid if, when interpreting each '(' as +1 and each ')' as -1, the cumulative sum is never negative and equals zero at the end. In other words, for a string s of length 2n, if we define \(S_i = \) (number of '(' in the first i characters) - (number of ')' in the first i characters), then for every \(1 \le i \le 2n\), it must hold that \(S_i \ge 0\) and \(S_{2n} = 0\).

inputFormat

The input consists of a single integer n (1 ≤ n ≤ 10) given on a single line, representing the number of pairs of parentheses.

outputFormat

Output all distinct valid combinations of n pairs of balanced parentheses, each printed on a new line, in lexicographical order.

1

()