22. Generate Parentheses

题目描述

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

思路

用DP，规律：
第一个括弧包含0个，后面跟n-1个：()(...)...
第一个括弧包含1个，后面跟n-2个：(())(...)...
第一个括弧包含2个，后面跟n-3个：((()))(...)...

具体做法

1. 新建一个存DP的list of list
2. 用double for loop循环，对于list中每个child list，都可以存放 新的括号“(” + “x个括号的各种排列” + “)” + “y个括号的各种排列”

    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        ans = [[] for a in range (n+1)]
        ans[0].append("")
        for i in range (n+1):
            for j in range (i):
                ans[i] += ["(" + x + ")" + y for x in ans[j] for y in ans[i-j-1]]
        return ans[n]