LeetCode 筆記 - 22. Generate Parentheses

題目在此 22. Generate Parentheses

給你 n 這個數字，請產生 n 個括號的所有組合。

Example 1:

Input: n = 3
Output: [“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

Example 2:
Input: n = 1
Output: [“()”]

解題思維

這題其實輸入才 1 ~ 8，應該是有人就直接寫死答案了 🤣

但我們在這裡不做這種事 😎

這題我們使用 backtracking，來產生所有組合即可。

程式碼

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

        def dfs(cur_result, open_count, close_count):
            if len(cur_result) == 2 * n:
                results.add(cur_result)
                return

            if open_count < n:
                dfs(cur_result + '(', open_count + 1, close_count)
            
            if close_count < open_count:
                dfs(cur_result + ')', open_count, close_count + 1)

        dfs('', 0, 0)
            
        return list(results)

解題思維

程式碼

也許你也會想看看