This problem is done with the idea of dynamic programming . Initialize a one-dimensional list to record The number of parentheses <= n All states , Such as dp[3] The logarithm containing parentheses is 3 All the sequences of . Just make sure that the sequence from the first state is correct , Design state transitions , You can ensure that all subsequent parenthesis sequences are correct
Initial conditions ：dp[0] = [""]
State shift ：temp = "(" + neck + ")" + tail, among neck Is the logarithm of parentheses m Sequence ( Taken from the dp[m] ),tail Is the logarithm of parentheses n Sequence ( Taken from the dp[n] ),temp Save in dp[m + n + 1] A list of
The code is simple , as follows ：
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
dp = [[] for _ in range(n + 1)]
dp[0].append("")
for pairs in range(1, n + 1):
# The number of parentheses you currently want
for tail_n in range(pairs):
# tail Bracket logarithm of part
for neck in dp[pairs - 1 - tail_n]:
for tail in dp[tail_n]:
temp = "(" + neck + ")" + tail
dp[pairs].append(temp)
return dp[-1]Another idea is to make use of a property of bracket sequence ,string[: n] Constant satisfaction ："(" The number of >= ")" The number of . Then use recursive functions to add characters one by one . Personally, I don't like recursion , do Fibonacci Lessons learned from the sequence . Use the stack if you can , Consider recursion if the stack is too complex
