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.
class Solution:
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
solutions = []
def __generateParenthesis(cur, left, right):
if left == 0 and 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 solutions
obj = Solution()
print(obj.generateParenthesis(4))