22. Generate Parentheses (String, Dynamic Programming, Backtracking)

링크 - https://leetcode.com/problems/generate-parentheses/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

backtracking을 통해서 풀 수 있는 문제이다.

Code

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        
        def dfs(cur_s, num_open, num_close):
            if num_open == n:
                while num_close < n:
                    cur_s += ")"
                    num_close += 1
                ans.append(cur_s)
                return

            dfs(cur_s + "(", num_open + 1, num_close)
            if num_open > num_close:
                dfs(cur_s + ")", num_open, num_close + 1)

        dfs("", 0, 0)
        return ans

Complexity

Time Complexity: O()

Space Complexity: O(n)