题解 | #括号生成#

Backtracking is also DFS but it is a little bit different from DFS. the nuance is we backtrack to the previous level of the tree so we have pop-off action once one brach ends. Then, in order to concatenate results from another branch, we need to trace back to one level up and so on to search there until all possible results are collected.

class Solution:
    def generateParenthesis(self , n ):
        # write code here
        res=[]
        def backtrack(left,right,s):
            #base case for one searching brach ends
            if left==0 and right==0:
                res.append(''.join(s))
                return 
            # add left parenthese as long as we have it left  
            if left>0:
                s.append('(')
                backtrack(left-1, right, s)
                s.pop()
            # add right parentthese when the left number of '(' is strictly less then 
            # the left number of ')'
            if left<right:
                s.append(')')
                backtrack(left, right-1, s)
                s.pop() 

        backtrack(n, n, [])
        return res