Given an integer pair_count, return all possible combinations of well-formed parentheses consisting of pair_count pairs. Each combination must be a string containing exactly pair_count opening ( and pair_count closing ) parentheses, arranged such that no closing parenthesis appears before its corresponding opening parenthesis.
Example 1
Input: 2
Output: [(()), ()()]
Explanation: There are two valid combinations for 2 pairs: (()) and ()().
Example 2
Input: 4
Output: [(((()))), ((()())), ((())()), ((()))(), (()(())), (()()()), (()())(), (())(()), (())()(), ()((())), ()(()()), ()(())(), ()()(()), ()()()()]
Explanation: All valid combinations for 4 pairs are listed.
Constraints
Case 1
Input: 3
Expected: ['((()))', '(()())', '(())()', '()(())', '()()()']
Case 2
Input: 5
Expected: ['((((()))))', '(((()())))', '(((())()))', '(((()))())', '(((())))()', '((()(())))', '((()()()))', '((()())())', '((()()))()', '((())(()))', '((())()())', '((())())()', '((()))(())', '((()))()()', '(()((())))', '(()(()()))', '(()(())())', '(()(()))()', '(()()(()))', '(()()()())', '(()())(())', '(()())()()', '(())((()))', '(())(()())', '(())(())()', '(())()(())', '(())()()()', '()(((())))', '()((()()))', '()((())())', '()((()))()', '()(()(()))', '()(()()())', '()(()())()', '()(())(())', '()(())()()', '()()((()))', '()()(()())', '()()(())()', '()()()(())', '()()()()()']
Case 3
Input: 1
Expected: ['()']