題目在此 22. Generate Parentheses
給你 n 這個數字，請產生 n 個括號的所有組合。
Example 1:
Input: n = 3
Output: [“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
Example 2:
Input: n = 1
Output: [“()”]
解題思維
這題其實輸入才 1 ~ 8，應該是有人就直接寫死答案了 🤣
但我們在這裡不做這種事 😎
這題我們使用 backtracking，來產生所有組合即可。
程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 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)
|
也許你也會想看看