Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
n 이라는 limit이 있으면,
여는 괄호 수를 openN, 닫는 괄호 수를 closeN이라고 했을 때
closeN <= openN이 되어야 한다.
closeN > openN이 되면 well-formed parentheses가 되지 못하기 때문이다.
아래와 같이 트리 구조를 그려보며 가능한 경우의 수를 생각해볼 수 있다.
풀이1: 백트래킹, stack 이용
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
stack = []
res = []
def backtrack(openN, closeN):
if openN == closeN == n:
res.append("".join(stack))
return
if openN < n:
stack.append("(")
backtrack(openN + 1, closeN)
stack.pop()
if closeN < openN:
stack.append(")")
backtrack(openN, closeN + 1)
stack.pop()
backtrack(0, 0)
return resstack에 현재까지 생성된 괄호를 저장한다. 재귀호출 중 추가/제거하며 상태를 유지한다.
유효한 괄호 조합은 res에 추가한다.
backtrack함수에서는 n이라는 limit, closeN < openN 이라는 조건에 따라 탐색을 제한하여 불필요한 조합 생성을 방지한다.
기저 조건(base case)은 열린 괄호와 닫힌 괄호의 개수가 각각 n에 도달할 때이고,
stack에 저장된 문자열을 res에 추가한다.
열린 괄호를 추가하거나, 닫힌 괄호를 추가하는 두 가지 선택지를 시도하되
조건에 맞지 않으면 더 이상 진행하지 않고 이전 상태로 돌아간다.
재귀 호출 후에는 추가했던 ( / ) 를 택에서 제거하고 다른 경로를 탐색할 수 있도록 한다.
백트래킹의 핵심 아이디어
1. 문제의 모든 경우를 탐색(가능성 있는 경우만)
2. 조건에 맞지 않는 경우 탐색을 멈춘다. (유효하지 않은 경로라면 되돌아감 : Pruning, 가지치기)
3. 되돌아간다(Backtracking) (특정 선택지가 정답으로 이어지지 않으면 이전 상태로 돌아가 다른 선택지를 시도한다.)
풀이2: 백트래킹, 스택 없이
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
def dfs(openN, closeN, s):
if openN == closeN and openN + closeN == n * 2:
res.append(s)
return
if openN < n:
dfs(openN + 1, closeN, s + "(")
if closeN < openN:
dfs(openN, closeN + 1, s + ")")
dfs(0, 0, "")
return res
이 풀이 역시
모든 경우를 탐색하지만 조건에 따라 가지치기를 수행하고,
탐색이 종료되면 되돌아간다는 점에서 백트래킹이라고 볼 수 있다.
풀이 1 과의 차이점은 스택 대신 문자열 s를 매번 업데이트하여 사용한다는 것이다.
백트래킹의 핵심은 "한 번 선택한 값을 기반으로 탐색을 진행하다가, 더 이상 진행이 불가능하면 되돌아가 다른 선택지를 탐색"하는 것이다.
시간 복잡도: 카탈란 수
가능한 조합의 수는 괄호 조합의 개수(카탈란 수)에 비례하며, 시간 복잡도는 대략 O(4^n / 루트 n) 으로 계산된다.
카탈란 수는 이진 트리 구조나 올바른 괄호 조합과 같은 특정 문제에서 등장하는 수학적 수열이다.
참고: https://en.wikipedia.org/wiki/Catalan_number
