22. Generate Parentheses

문제 링크 : https://leetcode.com/problems/generate-parentheses/

괄호를 결합할 수 있는 경우의 수 ..? 를 구하는 문제이다.

해당 문제를 푸는데 있어서 중요한 포인트는 두가지 이다.

1.주어진 n만큼 열린 괄호와 닫힌 괄호가 있음
ex. n=3 => opened=3(열린괄호), closed=3(닫힌 괄호)

2. 열린 괄호는 주어진 괄호 수 만큼 쓸 수 있음 그리고 닫힌 괄호는 열린 괄호보다 많을 수 없음

ex.n=3 => opened=3(열린괄호), closed=3(닫힌 괄호)
맨 처음 열린 괄호가 append되고 다음으로 올 수 있는 경우의 수는 열린 괄호나 닫힌 괄호 하나가 올 수 있다.

만약에 다음으로 열린 괄호가 들어온다면 그 다음으로 올 수 있는 경우의 수는 열린 괄호 혹은 닫힌 괄호가 올 수 있다.
이 떄 열린 괄호는 주어진 열린 괄호의 수를 넘길 수 없고 (ex.(((( -> X)
닫힌 괄호는 append된 열린 괄호의 수 보다 많을 수 없다 (ex. (()) ) -> X)

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

        def backtrack(opened,closed):
            if opened<n:
                stack.append("(")
                backtrack(opened+1,closed)
                stack.pop()
                
            if closed<opened:
                stack.append(")")
                backtrack(opened, closed+1)
                stack.pop()
                    
            if opened==closed==n:
                ans.append(''.join(stack))
                return
            
        backtrack(0,0)
        return ans

Runtime: 51 ms, faster than 48.11% of Python3 online submissions for Generate Parentheses.
Memory Usage: 14.2 MB, less than 38.91% of Python3 online submissions for Generate Parentheses.

22.08.29

다시 풀어봄

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        stack=[]
        
        def backt(opened, closed):
            if opened<n:
                stack.append('(')
                backt(opened + 1, closed)
                stack.pop() #gloal stack
                
            if closed<opened:
                stack.append(')')
                backt(opened, closed+1)
                stack.pop()
            if opened == closed == n:
                ans.append("".join(stack))
                return 
        backt(0,0)       
            
        
        return ans