22. Generate Parentheses

生成括号

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
给定一个n表示有几对小括号。然后写一个方程返回所有小括号可能组成的形式。

Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:
Input: n = 1
Output: ["()"]

Constraints:
1 <= n <= 8

思路

先想到的思路是列出三个'('，另外三个')'就在每个'('之间进行排列组合。
如n=3
'( 1 ( 2 ( 3 ' 再1，2，3之间进行另外三个括号的排列组合。如n3=3，'((()))'。n3=2, n2=1 或者n1=1 '(()())' '()(())'...
但是问题来了，如何在代码上实现排列组合呢。这个应该就是这道题目的难点。
只能选确定好最后一个，再逐个往前确定。
由于不确定总共有几个n，所以循环套循环是是肯定不行的。只能靠递归。
不知道是不是最近连续写的题目太多了，今天有点写不明白。暂时放弃

答案解析

暴力递归

class Solution(object):
    def generateParenthesis(self, n):
        def generate(A = []):
            if len(A) == 2*n:
                if valid(A):
                    ans.append("".join(A))
            else:
                A.append('(')
                generate(A)
                A.pop()
                A.append(')')
                generate(A)
                A.pop()

        def valid(A):
            bal = 0
            for c in A:
                if c == '(': bal += 1
                else: bal -= 1
                if bal < 0: return False
            return bal == 0

        ans = []
        generate()
        return ans

递归的思想就是将第n个和第n-1个找到一个关联方式。
在这里，可以讲第n个括号生成，看成是第n-1个之前加一个'(', ')'。最后判断左括号的数量和右括号的数量是否相同。不相同，则不是一个合格的括号序列。
在这里就真的属于是暴力法了，从‘(((((..’ 到最后的‘...))))))’全部循环一遍，找到其中合适的。相当于从一开始的‘全部都是（括号到最后每次减一，在减一的基础上，对剩下的几位括号进行填充并判断是否满足条件。
从valid函数中我们可以学到，通过一种可能性+1另一种可能性-1，来最后得到为零。则表示这两个成分在循环里面保持着相同的数量。

时间复杂度：O(2^{2n}*n)，对于 2^{2n}个序列中的每一个，我们用于建立和验证该序列的复杂度为 O(n)。

空间复杂度：O(n)，除了答案数组之外，我们所需要的空间取决于递归栈的深度，每一层递归函数需要 O(1) 的空间，最多递归 2n 层，因此空间复杂度为 O(n)。

回溯

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        def backtrack(S = [], left = 0, right = 0):
            if len(S) == 2 * n:
                ans.append("".join(S))
                return
            if left < n:
                S.append("(")
                backtrack(S, left+1, right)
                S.pop()
            if right < left:
                S.append(")")
                backtrack(S, left, right+1)
                S.pop()
        backtrack()
        return ans

回溯法就是每次在添加新的括号的时候，判断是添加 '(', ')' 哪一个括号。
这个方法和我的构想比较相像，但是我没有实现出来。
由于对left和right的括号进行了数量控制，所以最后出现的组合方式肯定是满足要求的。
先对left的数据进行添加左括号，然后回调。每次根据一种可能性扩展，然后回退，走另一种可能性。也可以看作深度优先。

按括号序列的长度递归

class Solution(object):
    def generateParenthesis(self, N):
        if N == 0: return ['']
        ans = []
        for c in range(N):
            for left in self.generateParenthesis(c):
                for right in self.generateParenthesis(N-1-c):
                    ans.append('({}){}'.format(left, right))
        return ans

这个代码看上去就很简单，将括号的添加设定为在括号中间添加left，和括号右边添加right。每次回调就在最外层套一个括号，或者在旁边放置一个括号。
设定left的个数c，N-1-c个right数。总共需要添加N-1个括号。

总结

这次学习耽误的时间比较长，再加上这里面有很多值得学习的地方。

1. 对称的两个东西的计数，可以通过-1和+1来进行。
2. 回调最主要是找到n和n-1之间的关系。
3. 括号这一类问题其实就是在括号里面添加或者在括号旁边添加。弄清楚问题的本质。