The Idea: Recursive build from the base case where if n = 0, then sol = { "" }, and if n = 1, then sol = { "()" }. If we continue this pattern, we will notice that every nth case can be built from n-1th case. That is, for every nth case, we insert a parenthesis pair "()" to every left parenthesis. Additionally, we insert a parenthesis pair at the beginning. To take care of duplicates, use an unordered_set. One big problem with this implementation is that we end up calculating a lot of redundent parenthesis sets.
Maintain two integers which will denote the number of remaining left and right parenthesis. Initially, we know that we need n left parenthesis and as a general rule, we can only have a right parenthesis if the current number of left parenthesis exceeds the number of right parenthesis. For example, if we have 0 left parenthesis, then there is no way we can have a right. However, when we have 2 left parenthesis - we can branch out with a right. So it follows that number of left parenthesis can only decrease, while the number or right parenthesis can only increase only when a left parenthesis is introduced.
classSolution:defgenerateParenthesis(self,n):""" :type n: int :rtype: List[str] """ solutions = []def__generateParenthesis(cur,left,right):if left ==0and right ==0: solutions.append(cur)else:if right:__generateParenthesis(cur +')', left, right -1)if left:__generateParenthesis(cur +'(', left -1, right +1)__generateParenthesis('', n, 0)return solutionsobj =Solution()print(obj.generateParenthesis(4))