[리트코드] 22. Generate Parentheses

# 문제 설명

n개의 괄호() 쌍이 주어질 때, 규칙에 맞게 잘 생성된 모든 괄호 조합을 반환해라.

 

# 입출력 예시

입력	출력
3	["((()))","(()())","(())()","()(())","()()()"]
1	["()"]

 

# 코드 풀이 1

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        paths = []
        def make_paths(path, cnt):
            if len(path) == n*2: # 모두 완성된 상태
                paths.append(path[:]) 
                return
            
            if cnt < 1: # '('개수가 다 들어간 상태
                make_paths(path+')', cnt)
                return
            if path.count('(')-path.count(')') < 1: # '('이 와야만 하는 상태
                make_paths(path+'(', cnt-1)
                return
            make_paths(path+'(', cnt-1)
            make_paths(path+')', cnt)
        make_paths('', n)
        return paths

 

# 코드 풀이 2: Backtracking

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        def backtrack(S = [], left = 0, right = 0):
            if len(S) == 2 * n:
                ans.append("".join(S))
                return
            if left < n: # '('가 가능하다면
                S.append("(")
                backtrack(S, left+1, right)
                S.pop()
            if right < left: # ')'가 가능하다면
                S.append(")")
                backtrack(S, left, right+1)
                S.pop()
        backtrack()
        return ans

 

# 코드 풀이 3: Closure Number

class Solution(object):
    def generateParenthesis(self, N):
        if N == 0: return ['']
        ans = []
        for c in xrange(N):
            for left in self.generateParenthesis(c):
                for right in self.generateParenthesis(N-1-c):
                    ans.append('({}){}'.format(left, right))
        return ans

N은 1보다 항상 크고, 언제나 (에서 시작하고 )으로 끝난다.

 

 

# 핵심 포인트

• n개의 괄호 쌍을 모두 사용해야 하므로 n*2 길이가 되면 답이 된다.
• 문자열의 + 연산은 원래 문자열에 영향을 미치지 않는다.