[ LeetCode - 22 ] Generate Parentheses

https://leetcode.com/problems/generate-parentheses/

Generate Parentheses - LeetCode

만들 수 있는 괄호의 수 n이 주어졌을 때 만들 수 있는 괄호의 형태의 가짓 수를 구하는 문제로 브루트 포스 문제!!

나는 백트래킹 기법을 이용해서 문제에 접근했다.

---

[ 📌 풀이 ]

1) 함수를 재귀호출 하는데 매 호출마다 추가되는 문자열의 옵션은 두 개 밖에 없다. '(', ')'

2) n이 3 주어졌다면 ()()() 총 3쌍이 문자열로 길이는 6 이니까 문자열의 절반이 n과 같을 때 해당 문자열의 재귀 호출을 멈춘다.

3) 문자열이 유효한 문자열인지 확인하기 위해서 valid 함수를 호출해서 유효 하다면 정답으로 넣는다.

[ 관계 시각화 ]

이렇게 그래프로도 문제 풀이가 가능하다.

모양은 그래프지만 백트래킹 기법도 이 모양과 같게 흘러간다.

---

[ 📌 코드 - Python ]

class Solution:
    answer = []
    opt = ["(", ")"]

    def generateParenthesis(self, n: int) -> list[str]:
        self.answer = []
        self.generate(n, "")
        return self.answer

    def generate(self, n: int, s: str) -> str:
        if len(s) / 2 == n:
            if self.isValid(s):
                self.answer.append(s)
            return
        
        for idx in range(2):
            self.generate(n, s + self.opt[idx])

    def isValid(self, s: str) -> bool:
        stack = []

        for word in s:
            if stack and (word == ")" and stack[-1] == "("):
                del stack[-1]
                continue
        
            stack.append(word)

        return len(stack) == 0

---

[ 📌 결과 ]

무수한 실패와 함께한다!!

[ Result ]