57 lines
1.6 KiB
Python
57 lines
1.6 KiB
Python
def generateParenthesis(n: int) -> list[str]:
|
|
"""
|
|
:type n: int
|
|
:rtype: List[str]
|
|
"""
|
|
# Attempted solution
|
|
# stack = []
|
|
# pairs = ""
|
|
# opening_brackets = {'('}
|
|
# closing_brackets = {')'}
|
|
# bracket_pairs = {')': '('}
|
|
|
|
# # Create n pairs
|
|
# for i in range(n):
|
|
# pairs += "()"
|
|
# # print(pairs)
|
|
|
|
# # Create and filter permutations
|
|
# for pair in permutations(pairs):
|
|
# parenthesis = "".join(pair)
|
|
# # print(pair)
|
|
# # print(parenthesis)
|
|
# if parenthesis in bracket_pairs.keys():
|
|
# if not stack or stack[-1] != bracket_pairs[parenthesis]:
|
|
# print('bad')
|
|
|
|
# Solution
|
|
def dfs(left, right, s):
|
|
print(f'left: {left}')
|
|
print(f'right: {right}')
|
|
print(f's: {s}')
|
|
|
|
|
|
# Check if the length of the string is double the size of n
|
|
# Example n=2, s= "(())"
|
|
# Returns the string once 6 characters have been filled out
|
|
if len(s) == n * 2:
|
|
res.append(s)
|
|
return
|
|
|
|
# Continuously fills left parenthesis until n
|
|
# Example: n = 2, s = "(", then stops at s="(("
|
|
if left < n:
|
|
# Recursive call to add more to the left
|
|
dfs(left + 1, right, s + '(')
|
|
|
|
# Continuously fills right parenthesis until it matches with the left
|
|
# Example: n = 2, s = "(()", then stops at s="(())"
|
|
if right < left:
|
|
# Recursive call to add more to the right
|
|
dfs(left, right + 1, s + ')')
|
|
|
|
res = []
|
|
dfs(0, 0, '')
|
|
# print(res)
|
|
return res
|
|
generateParenthesis(3) |