题解 | #括号生成#

括号生成

http://www.nowcoder.com/practice/c9addb265cdf4cdd92c092c655d164ca

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
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-04 14:35
点赞 评论 收藏
分享
fRank1e:吓得我不敢去外包了,但是目前也只有外包这一个实习,我还要继续去吗
点赞 评论 收藏
分享
05-09 14:45
门头沟学院 Java
点赞 评论 收藏
分享
ohs的小木屋:比不少实习待遇高了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务