Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Constraints:
1 <= n <= 8
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Input: n = 1
Output: ["()"]
We generate new combinations of well-formed parentheses based on previous iteration's results. Thus, it is a DP question.
Pattern 1: Add outer parenthesis by iterating previous results
dp[i] = set(['(' + x + ')' for x in dp[i-1]])
Pattern 2: Try all orders for all previous results and then perform set union.
# DP table has dp[1], dp[2], dp[3] and now compute for dp[4] (i=4)
# the following nested for loops will do:
# dp[i] |= set([x + y for x in dp[1] for y in dp[3]])
# dp[i] |= set([x + y for x in dp[2] for y in dp[2]])
# dp[i] |= set([x + y for x in dp[3] for y in dp[1]])
for j in range(1, i):
dp[i] |= set([x + y for x in dp[j] for y in dp[i-j]])
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
# ==================================================
# Dynamic Programming =
# ==================================================
dp = {1: set(['()']), 2: set(['(())', '()()'])}
# (base case)
if n == 1 or n == 2: return dp[n]
for i in range(3, n+1):
# pattern 1: outer parenthesis + subproblem with length - 1
dp[i] = set(['(' + x + ')' for x in dp[i-1]])
# pattern 2: dp[i] is formed by dp[j] + dp[i-j]
for j in range(1, i):
# perform set union on combinations of elements in dp[j] and dp[i-j]
dp[i] |= set([x + y for x in dp[j] for y in dp[i-j]])
return list(dp[n])
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
# (base case)
if n == 1: return ['()']
# ==================================================
# String + Set =
# ==================================================
ans = ['()']
for _ in range(n-1):
result = set()
# insert '()' in each index of string
# then using SET JOIN to combine without duplicate items
for string in ans : result |= self.insertParenthesis( string )
ans = result
return ans
def insertParenthesis(self, string) -> set:
ret = set()
for i in range(len(string)) : ret.add(string[:i] + '()' + string[i:])
return ret