Generate all parenthesis

You are given an integer ‘N’, your task is to generate all combinations of well-formed parenthesis having ‘N’ pairs. You are task is to generate all possible valid sets of parenthesis that can be formed with a given number of pairs.

A parenthesis is called well-formed if it is balanced i.e. each left parenthesis has a matching right parenthesis and the matched pairs are well nested.

For Example:

For ‘N’ = 3,
All possible combinations are: 
((()))
(()())
(())()
()(())
()()()

Input Format:

Input consists of a single line containing a single integer ‘N’, representing the number of pairs in the parentheses.

Output Format:

For each test case print list of strings denoting all possible combinations for the given integer. 

If there are multiple answers possible you have to print any one of them.

Note

You are not required to print anything, it has already been taken care of. Just implement the function.

Constraints:

1 <= N <= 11

Time Limit: 1 sec.