Leetcode: Generate parentheses
Given a strictly positive integer n, write a function that returns all possible combinations of well-formed parentheses.
Parentheses can be nested and added one after the other. It is important that we don’t create invalid combinations, such as )(. The idea then becomes to start with a single set of parentheses (). We can add another set of parentheses at three possible places: 1(2)3. When looking closely, we see that 1 and 3 are the same position.
We can then utilize Pythons string splitting capabilities which allow us to insert one or more characters at any place in the string. We do this by iterating over the string and inserting () at every possible position. This creates all valid pairs like (()) and ()() etc.
To avoid the aforementioned duplicates we can add a memory to the function and store all the visited possible combinations. This allows us to speed the process up significantly. For example when we visit ()(), we don’t need to visit it again to form ()()() or ()(()) (for n=3) because they would already been visited.
from typing import List
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
if n == 0:
return []
memo = set()
def inner(n, s):
if n == 0:
return [s]
res = []
for p in range(len(s)):
cand = s[:p] + '()' + s[p:]
if cand in memo:
continue
memo.add(cand)
res += inner(n-1, cand)
return res
res = inner(n-1, '()')
return res
if __name__ == '__main__':
s = Solution().generateParenthesis
print(s(0), [])
print(s(1), ['()'])
print(s(2), ['()()', '(())'])
print(s(3), ['((()))', '(()())', '(())()', '()(())', '()()()'])
2024 Update
When examining this problem again, I wanted to find a solution without memory overhead.class Solution:
def generateParenthesis(self, n: int) -> List[str]:
results = []
self.inner(0,0,n,[],results)
return results
def inner(self, left: int, right: int, n: int, path: List[str], result: List[str]) -> None:
if left == n and right == n:
result.append("".join(path))
if left < n:
path.append('(')
self.inner(left+1, right, n, path, result)
path.pop()
if right < left:
path.append(')')
self.inner(left, right+1, n, path, result)
path.pop()left parentheses to path, until it is no longer possible. Then it attempts to add right parentheses until left == right. At this point we know we have a valid output path gets transformed into a result: ((())).
Then the backtracking begins by going one level up and adding a right parentheses, going again a level deeper ((). Now it’s possible to add a left parenthesis again (()(, followed by two right parentheses. This ultimately yields all possible solutions without duplicates.