22. 括号生成[medium]

22. 括号生成[medium]

https://leetcode-cn.com/problems/generate-parentheses/

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：

输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

通过次数133,015 提交次数176,235

Second Try

2020-06-07

经过了0046题终于理解了回溯算法，而这里我不需要在第一个递归调用之后额外处理“回溯”的原因在于：

• 每次调用consump函数时候都对combine字符串进行了复制，并没有影响当前函数中字符串变量本身
• 每个consump函数在迭代到终局之后，被res收集后并没有返回什么内容，因此也不会干扰到当前函数中剩下的另一个调用，因此当前函数的第二个调用总归要被执行的

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        if n <= 0:
            return []
        rv = []
        def consump(combine, left, right, n, res):
            # print(combine)
            if right == n:
                res.append(combine)
                return 

            if left < n:
                consump(combine + "(", left + 1, right, n, res)
            if right < left:
                consump(combine + ")", left, right + 1, n, res)
        consump("", 0, 0, n, rv)
        return rv

• 执行用时 :16 ms, 在所有 Python 提交中击败了93.55%的用户
• 内存消耗 :12.7 MB, 在所有 Python 提交中击败了11.11%的用户

First Try

发现突然无法理解递归的细节了，尤其是递归中两种路线都可以的，比如这里的left<n和right<left两种同时可能。以前写的递归是多个子递归之间互不影响，出来个分段式影响的还是有点纠结。比如快排和merge sort, 都是分别对left和right部分进行递归，彼此并不影响。

不过这次尝试递归过程看起来是在第一个递归处一路怼到底，总觉得结果应该失败，但是执行测试发现竟然也能够通过。

在second try中终于理解了，重点学习下回溯算法的思路和缘由。

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        if n <= 0:
            return []
        rv = []
        def consump(combine, left, right):
            print(combine)
            if right == n:
                rv.append(combine)
                return 

            if left < n:
                consump(combine + "(", left + 1, right)
            if right < left:
                consump(combine + ")", left, right + 1)
        consump("", 0, 0)
        return rv

打印结果

debug 1

• input: 1
• output:
• stdout:

(
()

debug 2

• input 2
• output: ["(())","()()"]
• stdout:

(
((
(()
(())
()
()(
()()

debug 3

• input: 3
• output: ["((()))","(()())","(())()","()(())","()()()"]
• 运行过程中打印debug:

(
((
(((
((()
((())
((()))
(()
(()(
(()()
(()())
(())
(())(
(())()
()
()(
()((
()(()
()(())
()()
()()(
()()()

• 执行用时 :32 ms, 在所有 Python 提交中击败了22.77%的用户
• 内存消耗 :13.2 MB, 在所有 Python 提交中击败了11.11%的用户