[DSA][Backtracking] 06. Generate Parentheses

LeetCode 22

 

06. Generate Parentheses

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

 

 

[아이디어]

- '('의 개수가 ')'의 개수보다 많을 때만 ')'를 붙이며 backtracking 한다.

 

 

[풀이 1] Backtracking

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        def dfs(tmpStr, left, right):
            if left + right == 2 * n:
                res.append(tmpStr)
                return
            if left < n:
                dfs(tmpStr + "(", left + 1, right)
            if left > right:
                dfs(tmpStr + ")", left, right + 1)

        dfs("(", 1, 0)
        return res

Valid 한 괄호 문자열을 만들기 위해서는 항상 '('가 먼저 오고, 그 후에 ')'를 붙여야 한다. 따라서 backtracking을 통해 '('를 먼저 붙인 후에 열린 괄호의 개수가 닫힌 괄호의 개수보다 많을 때 ')'를 붙이면 항상 유효한 괄호 문자열을 만들 수 있다.

 

⏱️ 시간복잡도

시간복잡도는 "각 문자열을 생성하는 데 드는 시간" x "유효한 문자열의 개수"에 비례한다.

최종 문자열의 길이가 2n이므로 각 문자열을 생성하는 데는 O(n)이 걸리고 유효한 문자열의 개수는 아래와 같다.

따라서 전체 시간 복잡도는 O(4^n/√n)이다.

※ Cn은 "카탈란 수"인데 왜 유효한 문자열의 개수가 위와 같은지 별도의 포스팅에서 증명 과정을 다뤄보자.

​

🧠 공간복잡도

공간복잡도는 "유효한 문자열의 개수" x "문자열의 길이"이기 때문에, 전체 공간 복잡도도 O(Cn x n)으로 O(4^n/√n)이다.