leecode 22. Generate Parentheses 풀이

문제 :

아래와 같이 n이 주어질 때 ( 1 <= n <= 8 ) 가능한 parentheses를 모두 반환하라

 

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

Example 2:

Input: n = 1 Output: ["()"]

Follow up :

 

아이디어 : 처음에 '(' 를 path에 설정하여 ')' 갯수가 '(' 를 넘지 않도록 증가시키며 generate한다. 재귀를 통해 path를 생성하여 ans에 반환한다.

 

코드 :

 

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        global ans
        ans = []
        self.find(1, 0, '(', n)
        return ans
    def find(self, l, r, path, n):
        global ans
        if l == r and l == n:
            ans.append(path)
            return
        if l < r or n < l:
            return
        elif l == r:
            return self.find(l+1, r, path + '(', n)
        else:
            self.find(l, r+1, path + ')', n)
            self.find(l+1, r, path + '(', n)
            return

 

학습 포인트 : 시간복잡도는 괜찮은데 메모리 사용량이 많은 것은 재귀를 통해 path를 다수 생성해서 그런거같다. 다른 dp 풀이에서도 비슷하게 사용하는거 같은데 어떤 차이인지 알기 힘들다. python에서 string 다루는 법을 좀 더 익혀야겠다.

 

출처 : leetcode.com/problems/generate-parentheses/