22. Generate Parentheses

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

For example, given n = 3, a solution set is:

[ "((()))", "(()())", "(())()", "()(())", "()()()" ]

 

순열 조합 문제인 줄 알았으나 dfs로 풀기 때문에 브루트 포스, 그리디 문제 같다.

 

left는 넣을 수 있는 왼쪽 괄호의 개수, right는 넣을 수 있는 오른쪽 괄호의 개수이다.

left,right 하나씩 넣어주지만 오른쪽 괄호는 왼쪽 괄호가 하나이상 존재할 때만 넣을 수 있다.

left<right인 경우는 이미 왼쪽 괄호가 오른쪽 괄호보다 개수가 많이 존재하는 경우이므로 오른쪽 괄호를 넣을 수 있다.

 

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        
        def genParent(s,left,right,result):
            if left: genParent(s+'(',left-1,right,result) #왼쪽에 괄호를 더해준다
            if right>left:genParent(s+')',left,right-1,result) #right가 더 크면 왼쪽괄호가 이미 있다는 뜻(오른쪽 넣어도 된다)
            if not right: # 모든 괄호를 채웠을 경우
                result.append(s)
            return result #전체 배열 반환
        
        return genParent('',n,n,[])