LeetCode 刷题记录: 22. Generate Parentheses [Python]

原题

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

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

思路

使用动态规划，分析子问题：每次加括号要么加在外面，要么加在旁边。

代码

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        dp=[[] for i in range(n+1)]
        dp[0].append('')
        for i in range(n+1):
            for j in range(i):
                dp[i]+=['('+inner+')'+outer for inner in dp[j] for outer in dp[i-j-1]]
        return dp[n]