2020-03-06 Day13 Leetcode: 22. G

class Solution:
    def generateParenthesis(self, n: int):
        if n==1:
            return ["()"]
        result=[]
        for item in self.generateParenthesis(n-1):
            if item+"()" == "()"+item:
                result.append(item+"()")
            else:
                result.append(item+"()")
                if "()"+item not in result:
                    result.append("()"+item)
            result.append( "("+item+")")

        return result

class Solution:
    def generateParenthesis(self, n: int):
        if n<1:
            return []
        result=[]
        
        left=right=0
        tempresult=""
        self.backtracking(result, tempresult, left, right, n)
        return result
    
    def backtracking(self, result,tempresult,left,right,n):
        if len(tempresult)==n*2:
            result.append(tempresult)
        
        if left<n:
            tempresult+='('
            self.backtracking(result,tempresult,left+1,right,n)
            tempresult=tempresult[:-1]
            
        if right<left:
            tempresult+=')'
            self.backtracking(result,tempresult,left,right+1,n)
            tempresult=tempresult[:-1]