題目

數字?n?代表生成括號的對數，請你設計一個函數，用于能夠生成所有可能的并且?有效的?括號組合。

示例

示例 1：

輸入：n = 3
輸出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

輸入：n = 1
輸出：["()"]

分析

為了生成所有可能的并且有效的括號組合，可以使用回溯算法。回溯算法通過遞歸的方式，嘗試所有可能的括號組合，并在生成過程中確保組合的有效性。

回溯法

代碼解釋

回溯函數?backtrack：

open：當前已經使用的左括號的數量。

close：當前已經使用的右括號的數量。

max：括號的對數。

當?current?的長度達到?2 * max?時，說明已經生成了一個完整的括號組合，將其添加到?result?中。

如果?open?小于?max，可以添加一個左括號，并遞歸調用?backtrack。

如果?close?小于?open，可以添加一個右括號，并遞歸調用?backtrack。

時間復雜度：O()

空間復雜度：O()

class Solution {
private:// 回溯函數，用于生成括號組合void backtrack(std::vector<std::string>& result, std::string current, int open, int close, int max) {// 當當前組合的長度達到 2 * max 時，說明已經生成了一個完整的括號組合if (current.length() == max * 2) {result.push_back(current);return;}// 如果左括號的數量小于 max，則可以添加一個左括號if (open < max) {backtrack(result, current + '(', open + 1, close, max);}// 如果右括號的數量小于左括號的數量，則可以添加一個右括號if (close < open) {backtrack(result, current + ')', open, close + 1, max);}}
public:std::vector<std::string> generateParenthesis(int n) {std::vector<std::string> result;backtrack(result, "", 0, 0, n);return result;}
};