Leetcode 22. Generate Parentheses

문제

Given n pairs of parentheses,
write a function to generate all combinations of well-formed parentheses.

주어진 n개의 괄호 쌍에 대해
가능한 모든 괄호의 조합을 리턴하시오.

예시

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

제한

• 1 <= n <= 8

풀이법

제한에서 볼수 있듯이, 거의 없이 때문에

모든 경우를 전부 계산하도록 한다.

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        dp = [set() for _ in range(n+1)]
        dp[1].add("()")

        for i in range(2, n+1):
            for v in dp[i-1]:
                dp[i].add("()" + v)
                dp[i].add(v + "()")
                dp[i].add("("+v+")")
            for k in range(1, i):
                for p in range(1, i):
                    if k + p != i: continue
                    kv = dp[k]
                    pv = dp[p]
                    for kvs in kv:
                        for pvs in pv:
                            dp[i].add(kvs + pvs)
                            dp[i].add(pvs +  kvs)
        return list(dp[n])