https://leetcode.com/problems/generate-parentheses/
모든 경우에 대해서 만들어야 합니다.
모든 경우에 대해서 만들어야 하기 때문에 NP 문제이다.
총 n 개의 괄호을 만들경우,
왼쪽에 k 개, 오른쪽에 n-k 개가 있는경우,
또는 전체을 괄호가 감싸고, 왼쪽에 k 개 오른쪽에 n-k-1 개가 있는 경우가 있습니다.
중복을 제거하기 위해서 set 을 사용하였습니다.
class Solution:
# n 에 대해서는 불변이기 때문에 memorization 을 사용
@functools.lru_cache(None)
def generateParenthesis(self, n: int) -> List[str]:
if n == 0:
return ['']
if n == 1:
return ['()']
ret = set()
for k in range(1, n):
ls, rs = self.generateParenthesis(k), self.generateParenthesis(n-k)
for l in ls:
for r in rs:
ret.add(l+r)
for k in range(1, n):
ls, rs = self.generateParenthesis(k), self.generateParenthesis(n-k-1)
for l in ls:
for r in rs:
ret.add(f'({l}{r})')
return ret