LeetCode #22: Generate Parentheses
β’ 122 words β’ 1 min β’ updated
LeetCode #22: Generate Parentheses:
python
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
ans = []
def backtrack(n, o, s):
assert n >= 0
if n == 0:
assert s
ans.append(s + ')' * o)
return
# (
backtrack(n - 1, o + 1, s + '(')
# )
if o > 0:
backtrack(n, o - 1, s + ')')
backtrack(n, 0, "")
return ansIn each node, decide whether to add ‘(’ or ‘)’.
n keeps track of available ‘(’.
o keeps track of available ‘)’.
Strings in Python are immutable, making it easier to backtrack.
If we used an array, then we would have to employ a pattern like this:
python
s.append('(')
backtrack(n - 1, o + 1, s)
s.pop()