n개의 괄호쌍 만들기

                                    🤔 순열과 조합이다
>>> 이런건 보통 backtracking으로 풀었던 것 같은데...
>>> ✅ DFS로 가능한 모든 경우의수를 선택할 수 있다.

                                    ✅ )는 무조건 (이 있어야 선택 될 수 있다.

✅ ( 뒤에는 )혹은 (를 선택해야 한다.

✅ n값이 주어지면 가장 처음 (를 넣는다.

✅ n값에 맞춰 ( 혹은 )를 결정해야한다.
>>> n = 1이라면 초기값에 의해 다음은 )밖에 없다.
>>> n = 2이라면 초기값에 의해 (이 이미 선택되었으니, ( 혹은 )를 넣어야 한다.

✅ 전에 )이 선택되었다면 괄호가 완성된 것이니 다음값은 무조건 (이다.
>>> if before == ')' then must choice "("

✅ 각 단계에서 가능한 모든 경우의 수로 뻗어 나가자
>>> 배운 backtracking 활용

🗝️ 종료조건
>>> 만들어진 string이 n크기 여야 한다.

                                    class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """

        result = []
        def dfs(parent, left):

            if len(parent) == n * 2:
                print("parent, ", parent)
                result.append(parent)
                return

            if parent[-1] == "(":
                if left < n:
                    left += 1
                    dfs(parent + "(", left + 1)
                    dfs(parent + ")", left)
                else:
                    dfs(parent + ")", left)

            elif parent[-1] == ")":
                dfs(parent + "(", left + 1)

        dfs("(", 1)

        return result

                                    ✏️ 논리 수정하기

✅ left처럼 right에도 제한을 둬야한다.
>>> left < right가 되는 경우의 수를 모두 제거해야한다.
ex) n = 2 -> ()) 와 같은 경우 \

🗝️ 항상 right는 left보다 작거나 같아야 함을 알 수 있다.

✅ 이전 값을 볼 필요는 없다. 그냥 left, right 만 보면 된다.

                                    class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """

        result = []
        def dfs(parent, left, right):

            if len(parent) == n * 2:
                result.append(parent)
                return

            if left < right:
                return

            if left == n:
                dfs(parent + ")", left, right + 1)
            else:
                dfs(parent + "(", left + 1, right)
                dfs(parent + ")", left, right + 1)

        dfs("(", 1, 0)

        return result

# n = 3
# (
# (((
# ()