[리트코드] 22. Generate Parentheses

리트코드 22번 문제.

난이도: Medium

 

문제

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

1 <= n <= 8

괄호 n개를 이용해서 만들 수 있는 모든 괄호 combination을 리턴하는 function을 짜야한다

 

예시

Example 1

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

Example 2:

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

 

답

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []

        def backtracking(paren, op, cl):
            if len(paren) == 2 * n:
                res.append(paren)
            else:
                if op < n:
                    backtracking(paren + "(", op + 1, cl)
                if cl < op:
                    backtracking(paren + ")", op, cl + 1)

        backtracking("", 0, 0)

        return res

Time Complexity: O(2^2n)

 

설명

이 문제의 핵심은 백트래킹이다. 백트래킹이란 모든 경우의 수를 전부 고려하여 답을 체크하는 방식으로 현재 상태에서 가능한 모든 답 "후보"들을 찾아내 처음 후보부터 깊이 들어갔다가 모든 경우의 수를 고려했거나 조건에 맞지 않으면 다시 회귀하는 알고리즘이다. 

이미지 1: 백트래킹 알고리즘

백트래킹은 주어진 상태 (혹은 노드)가 있고 그 상태의 parameter를 하나씩 바꿔가면서 다른 루트를 검색하는 것이다. 예를 들어 이 문제의 노드는 (paren, op, cl)이다. paren은 현재 만든 parenthesis string이고 op은 지금까지 소진한 opening bracket, cl은 지금까지 소진한 closing bracket이다. 처음 상태는 ("", 0, 0)이 된다.

 

이 문제 백트래킹에서는 3가지 condition이 있다.

1. op < n: 이 때는 아직 더 opening bracket을 쓸 수 있을 때이다. backtracking을 호출해 backtracking(paren + "(", op + 1, cl)을 검색한다.
2. cl < op: 이 때는 closing bracket이 opening bracket보다 적을 때이다. 이 때는 언제든지 bracket 하나를 닫을 수 ㅗ. 그러므로 backtracking을 호출해 backtracking(paren + ")", op, cl + 1)을 검색한다.
3. len(paren) == 2*n: 이 경우는 valid 한 parenthesis를 만들었을 때이다. 이 backtracking알고리즘은 조건에 맞지 않는 상태는 만들지 않으므로 괄호 combination이 valid 하다고 가정할 수 있다.

이 원리를 이용하여 처음 상태의 노드 ("", 0, 0)에서 backtracking을 시작한다. 참고로 backtracking 함수는 python에서 inner-function으로 함수 바깥에 있는 variable을 쓸 수 있다. 그래서 이 코드에서는 res와 n을 썼다. 마지막에는 valid 한 parentheses를 모은 res를 리턴하면 된다.

 

마지막으로 이문제에서 백트래킹과 brute force method가 다른 점은 백트래킹은 가능한 "후보"만 consider 한다는 것이다. 예를 들어 brute force method는  if op < n과  if cl < op를 체크하지 않고 일단 2n길이의 string을 만들고 마지막에 valid parenthesis인지 체크하는 방식일 것이다. 백트래킹은 주어진 상태에서 나아갈 수 있는 루트를 확인하고 그 루트만 고려하여 더 탐색한다. 그러므로 백트래킹이 brute force depth first search보다 더 효율적인 방법이라고 할 수 있다.

 

짧은 답

...

 

노트

이 문제도 되게 잘 만들어진 문제이다. 기본적인 알고리즘 중 하나인 backtracking의 원리를 파악할 수 있고 3 valid conditions이 정말 쉽고 명백하게 보이지는 않기 때문에 꽤 생각이 필요한 문제다. 인터뷰에서도 backtracking을 쓰는 candidates와 일반적인 BFS/DFS를 쓰는 candidates를 구별할 수도 있기 때문에 인터뷰에서도 많이 보인다.

 

출처

이미지 1: https://en.wikipedia.org/wiki/Backjumping#/media/File:Backtracking-no-backjumping.svg