查看: 1120|回复: 0
收起左侧

Leetcode 22 Generate Parentheses 递归过程

|只看干货 |刷题

分享帖子到朋友圈
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (51)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
这道题解题思路已经明白了,但有人可以帮忙解释一下递归过程么?

code如下
  1. class Solution(object):
  2.     def func(self, ans, strs, left, right, nmax):
  3.         print("start new func: ", left, right, strs, nmax, ans)
  4.         if(left < nmax):
  5.             self.func(ans, strs + '(', left + 1, right, nmax)
  6.         if(right < left):
  7.             self.func(ans, strs + ')', left, right + 1, nmax)
  8.         if(len(strs) == 2 * nmax):
  9.             ans.append(strs)
  10.             return
  11.         
  12.     def generateParenthesis(self, n):
  13.         """
  14.         :type n: int
  15.         :rtype: List[str]
  16.         """
  17.         ans = []
  18.         self.func(ans, "", 0, 0, n)
  19.         print("main + ", ans)
  20.         return ans
复制代码


print出来的递归过程:
  1. ('start new func: ', 0, 0, '', 3, [])
  2. ('start new func: ', 1, 0, '(', 3, [])
  3. ('start new func: ', 2, 0, '((', 3, [])
  4. ('start new func: ', 3, 0, '(((', 3, [])
  5. ('start new func: ', 3, 1, '((()', 3, [])
  6. ('start new func: ', 3, 2, '((())', 3, [])
  7. ('start new func: ', 3, 3, '((()))', 3, [])
  8. ('start new func: ', 2, 1, '(()', 3, ['((()))'])
  9. ('start new func: ', 3, 1, '(()(', 3, ['((()))'])
  10. ('start new func: ', 3, 2, '(()()', 3, ['((()))'])
  11. ('start new func: ', 3, 3, '(()())', 3, ['((()))'])
  12. ('start new func: ', 2, 2, '(())', 3, ['((()))', '(()())'])
  13. ('start new func: ', 3, 2, '(())(', 3, ['((()))', '(()())'])
  14. ('start new func: ', 3, 3, '(())()', 3, ['((()))', '(()())'])
  15. ('start new func: ', 1, 1, '()', 3, ['((()))', '(()())', '(())()'])
  16. ('start new func: ', 2, 1, '()(', 3, ['((()))', '(()())', '(())()'])
  17. ('start new func: ', 3, 1, '()((', 3, ['((()))', '(()())', '(())()'])
  18. ('start new func: ', 3, 2, '()(()', 3, ['((()))', '(()())', '(())()'])
  19. ('start new func: ', 3, 3, '()(())', 3, ['((()))', '(()())', '(())()'])
  20. ('start new func: ', 2, 2, '()()', 3, ['((()))', '(()())', '(())()', '()(())'])
  21. ('start new func: ', 3, 2, '()()(', 3, ['((()))', '(()())', '(())()', '()(())'])
  22. ('start new func: ', 3, 3, '()()()', 3, ['((()))', '(()())', '(())()', '()(())'])
  23. ('main + ', ['((()))', '(()())', '(())()', '()(())', '()()()'])
  24. ["((()))", "(()())", "(())()", "()(())", "()()()"]
复制代码


这里
  1. ('start new func: ', 3, 3, '((()))', 3, [])
  2. ('start new func: ', 2, 1, '(()', 3, ['((()))'])
复制代码


为什么可以从(3,3)直接返回到(2,1),函数具体是如何进行返回的呢?先谢谢各路大神了。。。

评分

参与人数 2大米 +13 收起 理由
croatia + 3 给你点个赞!
Jerry_37 + 10

查看全部评分


上一篇:35岁妈妈 想学CS 求建议
下一篇:Bit Manipulation需要了解吗?
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

>
快速回复 返回顶部 返回列表