登录
  • #刷题

Leetcode 22 Generate Parentheses 递归过程

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

code如下

class Solution(object):[br][/br][br][/br]    def func(self, ans, strs, left, right, nmax):[br][/br][br][/br]        print("start new func: ", left, right, strs, nmax, ans)[br][/br][br][/br]        if(left < nmax):[br][/br][br][/br]            self.func(ans, strs + '(', left + 1, right, nmax)[br][/br][br][/br]        if(right < left):[br][/br][br][/br]            self.func(ans, strs + ')', left, right + 1, nmax)[br][/br][br][/br]        if(len(strs) == 2 * nmax):[br][/br][br][/br]            ans.append(strs)[br][/br][br][/br]            return[br][/br][br][/br]        [br][/br][br][/br]    def generateParenthesis(self, n):[br][/br][br][/br]        """[br][/br][br][/br]        :type n: int[br][/br][br][/br]        :rtype: List[str][br][/br][br][/br]        """[br][/br][br][/br]        ans = [][br][br][/br]        self.func(ans, "", 0, 0, n)[br][/br][br][/br]        print("main + ", ans)[br][/br][br][/br]        return ans


print出来的递归过程:

('start new func: ', 0, 0, '', 3, [])[br][br][/br]('start new func: ', 1, 0, '(', 3, [])[br][br][/br]('start new func: ', 2, 0, '((', 3, [])[br][br][/br]('start new func: ', 3, 0, '(((', 3, [])[br][br][/br]('start new func: ', 3, 1, '((()', 3, [])[br][br][/br]('start new func: ', 3, 2, '((())', 3, [])[br][br][/br]('start new func: ', 3, 3, '((()))', 3, [])[br][br][/br]('start new func: ', 2, 1, '(()', 3, ['((()))'])[br][/br][br][/br]('start new func: ', 3, 1, '(()(', 3, ['((()))'])[br][/br][br][/br]('start new func: ', 3, 2, '(()()', 3, ['((()))'])[br][/br][br][/br]('start new func: ', 3, 3, '(()())', 3, ['((()))'])[br][/br][br][/br]('start new func: ', 2, 2, '(())', 3, ['((()))', '(()())'])[br][/br][br][/br]('start new func: ', 3, 2, '(())(', 3, ['((()))', '(()())'])[br][/br][br][/br]('start new func: ', 3, 3, '(())()', 3, ['((()))', '(()())'])[br][/br][br][/br]('start new func: ', 1, 1, '()', 3, ['((()))', '(()())', '(())()'])[br][/br][br][/br]('start new func: ', 2, 1, '()(', 3, ['((()))', '(()())', '(())()'])[br][/br][br][/br]('start new func: ', 3, 1, '()((', 3, ['((()))', '(()())', '(())()'])[br][/br][br][/br]('start new func: ', 3, 2, '()(()', 3, ['((()))', '(()())', '(())()'])[br][/br][br][/br]('start new func: ', 3, 3, '()(())', 3, ['((()))', '(()())', '(())()'])[br][/br][br][/br]('start new func: ', 2, 2, '()()', 3, ['((()))', '(()())', '(())()', '()(())'])[br][/br][br][/br]('start new func: ', 3, 2, '()()(', 3, ['((()))', '(()())', '(())()', '()(())'])[br][/br][br][/br]('start new func: ', 3, 3, '()()()', 3, ['((()))', '(()())', '(())()', '()(())'])[br][/br][br][/br]('main + ', ['((()))', '(()())', '(())()', '()(())', '()()()'])[br][/br][br][/br]["((()))", "(()())", "(())()", "()(())", "()()()"]


这里
('start new func: ', 3, 3, '((()))', 3, [])[br][br][/br]('start new func: ', 2, 1, '(()', 3, ['((()))'])


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

发表回复