[리트코드 22] 괄호 조합 생성 — DFS 백트래킹

원제: Generate Parentheses

문제 요약

여는 괄호와 닫는 괄호가 각각 n개인, 올바르게 짝지어진 모든 문자열을 생성합니다. 제출 함수 generateParenthesis는 이 문자열들을 담은 리스트 answer를 반환합니다.

조건과 입출력

입력은 괄호 쌍의 수 n이며, 1 <= n <= 8입니다. 원문 예제: n = 3의 출력은 ["((()))","(()())","(())()","()(())","()()()"]로, 길이 6인 모든 올바른 조합입니다. n = 1의 출력은 ["()"]입니다.

예제와 문제 자료

원문 예제 1: Input: n = 3, Output: ["((()))","(()())","(())()","()(())","()()()"]. 원문 예제 2: Input: n = 1, Output: ["()"].

풀이 아이디어

DFS(stack, cnt, level)은 현재까지 만든 문자 목록 stack, 아직 짝을 기다리는 여는 괄호 수 cnt, 사용한 문자 수 level을 상태로 둡니다. 닫는 괄호는 cnt > 0일 때만 추가하므로 여는 괄호보다 닫는 괄호가 많아지는 접두사는 만들지 않습니다. 여는 괄호는 2*n - level > cnt일 때 추가합니다. 남은 칸 수가 현재 미완성 쌍 수 cnt보다 커야 닫는 괄호를 모두 배치하고도 여는 괄호를 하나 더 넣을 수 있기 때문입니다. 따라서 불가능한 접두사를 확장하지 않고, 길이가 2*n인 균형 문자열만 결과에 넣습니다.

코드의 핵심

DFS([], 0, 0)에서 시작합니다. cnt > 0이면 )를 붙여 cnt를 줄이고, 호출이 끝나면 stack.pop()으로 해당 선택을 되돌립니다. 여는 괄호 조건을 만족하면 (를 붙여 cnt를 늘린 뒤 같은 방식으로 되돌립니다. 이처럼 한 경로의 선택을 다음 경로에 남기지 않습니다.

level == 2*n이면 길이가 다 찬 상태입니다. 이때 cnt == 0인 문자열만 answer에 추가하고 즉시 반환합니다. cnt > 0이면 결과에는 넣지 않으며, 이어지는 조건도 더 이상 유효한 길이의 완성을 만들지 않습니다.

제출 코드

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        answer = []
        def DFS(stack, cnt, level):
            nonlocal answer
            if level == 2*n:
                if cnt == 0:
                    answer.append("".join(stack))
                    return

            if cnt > 0:
                stack.append(")")
                DFS(stack,cnt-1,level+1)
                stack.pop()

            if 2*n - level > cnt:
                stack.append("(")
                DFS(stack,cnt+1, level+1)
                stack.pop()
        
        DFS([],0,0)
        
        return answer

복잡도

유효한 괄호 문자열의 개수를 C_n이라 하면, 각 문자열의 길이는 2n이므로 결과 생성에 드는 시간은 O(n C_n)입니다. 재귀 깊이와 경로 저장용 stack은 각각 최대 2n 수준이어서 보조 공간은 O(n)입니다. 반환 목록 자체는 문자열 저장 공간으로 O(n C_n)을 사용합니다.

복습 포인트

괄호를 닫을 수 있는지는 cnt > 0, 여는 괄호를 더해도 완성이 가능한지는 남은 칸과 cnt의 비교로 판단합니다. 완료 시점에도 cnt == 0을 확인해 균형이 맞지 않는 문자열을 제외합니다.

출처

문제 원문