題目詳情
數字 n 代表生成括號的對數，設計一個函數生成所有可能的并且有效的括號組合。
示例 1：
輸入：n = 3
輸出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
示例 2：
輸入：n = 1
輸出：[“()”]
提示：
1 <= n <= 8
解題思路
使用回溯法（深度優先搜索） 生成所有有效括號組合，核心思路如下：
- 有效括號條件：
- 左括號數量不能超過
n。 - 右括號數量不能超過左括號（確保有效性）。
- 遞歸終止條件：當前字符串長度達到
2n時，將結果加入列表。 - 遞歸過程：
- 若左括號數量
< n，添加左括號并遞歸。 - 若右括號數量
< 左括號數量，添加右括號并遞歸。
- 回溯：每次遞歸后刪除最后一個字符，嘗試其他組合。
- 優化：使用
StringBuilder避免字符串拼接開銷，減少內存消耗。
代碼實現（Java版）
import java.util.ArrayList;
import java.util.List;class Solution {public List<String> generateParenthesis(int n) {List<String> result = new ArrayList<>();backtrack(result, new StringBuilder(), 0, 0, n);return result;}private void backtrack(List<String> result, StringBuilder current, int left, int right, int n) {if (current.length() == 2 * n) {result.add(current.toString());return;}if (left < n) {current.append('(');backtrack(result, current, left + 1, right, n);current.deleteCharAt(current.length() - 1); // 回溯}if (right < left) {current.append(')');backtrack(result, current, left, right + 1, n);current.deleteCharAt(current.length() - 1); // 回溯}}
}
代碼說明
- 初始化：
result存儲最終結果，StringBuilder current動態構建當前組合。
- 回溯函數：
- 參數：
left（已用左括號數）、right（已用右括號數）、n（總對數）。 - 終止條件：
current.length() == 2 * n時保存有效組合。 - 左括號分支：當
left < n時，添加(并遞歸。 - 右括號分支：當
right < left時，添加)并遞歸。 - 回溯操作：遞歸返回后刪除末尾字符，恢復狀態嘗試其他分支。
- 效率關鍵：
- 通過條件剪枝避免無效組合。
StringBuilder減少字符串操作開銷。
提交詳情（執行用時、內存消耗）
Kubernetes基礎介紹)
)
