[Leetcode]22. 括号生成

题目描述：

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

我的方法：

一种思路是列出所有可能性，排除其中不合法的组合。这种方法的时间复杂度高达O()。这自然不是一种经济的方法。

如果仔细考察结果，我们能够发现合法的结果符合以下特征：

1. 最左边一定是左括号“（”，最右边的一定是右括号“）”。
2. 都是由3个左括号、3个右括号构成。
3. 也许可以用递归，合法字符串剔除两个最内层的括号之后，剩余的部分依然合法。
4. 每个合法字符串必然至少有一对最内层的括号，当然也可以有嵌套的括号。

最终是使用递归方法来处理的。正如之前所述，递归需要考虑移动和终止条件两个因素。

中文网站居然报错（而且显然是网站自身问题导致的报错），只好去leetcode英文网站来提交了。效果一般，但总算没有超时。Runtime: 88 ms, faster than 5.64% of Python online submissions for Generate Parentheses.Memory Usage: 12.2 MB, less than 5.02% of Python online submissions for Generate Parentheses.

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        if n==1:
            return ["()"]
        # n对括号可以认为是n-1和1对括号的组合
        # 其中这1对括号可以看成是一个整体，同时移动
        ans=[]
        for ele in self.generateParenthesis(n-1):
            for i,v in enumerate(ele):
                tmp=ele[:i]+'()'+ele[i:]
                if tmp not in ans:
                    ans.append(tmp)
        return ans

别人的方法：

用的是回溯，这个方法算是新技能，直观上不太容易理解。回溯就是通过不同的尝试来生成问题的解。有点类似于穷举，但是和穷举不同的是回溯会“剪枝”，意思是对已知错误的结果没必要再继续尝试了。

回溯的步骤如下：

1. 定义合法的搜索结果：左括号的数量等于n，并且右括号的数量等于n。凡是合法的搜索结果，便加入到数组ans中。
2. 定义括号生成的路径，也可以理解成是树生成的路径。只有在两种情况下，才可能生成合法的树。
3. 一种生长路径是：左括号的数量l小于n时，可以对字符串s增加左括号，每次增加一个左括号。
4. 另一种生长路径是：当左括号的数量l>右括号数量r时，可以对字符串s增加右括号，每次增加一个右括号。
5. 通过递归调用，这两种生长路径可能会相互以不同的顺序穿插，从而生成不同的合法字符串s。

效果有所提升：执行用时 : 36 ms, 在Generate Parentheses的Python提交中击败了33.55% 的用户。内存消耗 : 12.2 MB, 在Generate Parentheses的Python提交中击败了0.00% 的用户

class Solution(object):
    def generateParenthesis(self, N):
        res=[]
        def backtrack(s,n,l,r):
            if l==n and r==n:
                res.append(s)
                return 
            if l<n:
                # 注意：这里是调用，而无需返回。
                # 每一次调用，都可能生成合法结果
                backtrack(s+'(',n,l+1,r)
            if l>r:
                backtrack(s+')',n,l,r+1)
        # 注意backtrack()并不返回任何值，只是改变了变量res的值
        backtrack('',N,0,0)
        # 最终输出res即可
        return res