22-括号生成

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

---

示例

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

---

解法

解法-动态规划

核心思想：分治算法/动态规划

在求N个括号的排列组合时，把第N种情况（也就是N个括号排列组合）视为单独拿一个括号E出来，剩下的N-1个括号分为两部分，P个括号和Q个括号，P+Q=N-1，然后这两部分分别处于括号E内和括号E的右边，各自进行括号的排列组合。

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        if n == 0: 
            return ['']
        res = []
        for i in range(n):
            for left in self.generateParenthesis(i):
                for right in self.generateParenthesis(n - 1 - i):
                    # 先拿出一对括号
                    # 剩下的括号要么在这一组新增的括号内部，
                    # 要么在这一组新增括号的外部（右侧）。
                    res.append('({}){}'.format(left, right))
        return res

解法-回溯算法

核心思想：类似深度优先，第一个结果，会是 ((())) ,最后一个结果是 ()()() 。

# 回溯法
class Solution:
    def generateParenthesis(self, N: int) -> List[str]:
        ans = []
        def backtrack(S = '', left = 0, right = 0):
            if len(S) == 2 * N:
                ans.append(S)
                return
            if left < N:
                backtrack(S+'(', left+1, right)
            if right < left:
                backtrack(S+')', left, right+1)

        backtrack()
        return ans

---

来源

LeetCode中该题地址，Click here!