1. 題目解析

題目鏈接：22. 括號生成

這個問題的理解其實相當簡單，只需看一下示例，基本就能明白其含義了。

2.算法原理

問題描述

我們需要找出所有可能的、有效的括號序列。一個有效的括號序列指的是一個僅由'('和')'組成的字符串，并且滿足以下條件：

1. 左括號的數量始終大于等于右括號的數量，從左到右遍歷字符串時。
2. 左括號的總數與右括號的總數相等。

遞歸策略

我們采用遞歸的方法來解決這個問題。遞歸的核心在于，在每一步，我們都有兩種選擇：放置一個左括號或（在條件允許的情況下）放置一個右括號。

遞歸函數設計

void dfs(std::string& current, int step, int left)

• current: 存儲當前構建的括號序列的字符串。
• step: 當前需要填入的位置（即current字符串的長度）。
• left: 當前狀態的字符串中已放置的左括號數量。

遞歸流程

1. 遞歸結束條件：
   • 當step等于目標長度（即2倍的括號對數）時，檢查current是否為一個有效的括號序列。如果是，則將其加入答案列表中。
2. 放置左括號：
   • 如果left小于目標長度的一半（即剩余的位置足夠放置等量的右括號），則可以在current的第step個位置放置一個左括號，并遞歸調用dfs函數，參數更新為step+1和left+1。遞歸完成后，需要撤銷這個左括號的放置，以便嘗試其他可能性。
3. 放置右括號：
   • 如果當前已放置的右括號數量（step - left）小于已放置的左括號數量left，則可以在current的第step個位置放置一個右括號，并遞歸調用dfs函數，參數更新為step+1和left（因為右括號的放置不影響左括號的數量）。同樣，遞歸完成后需要撤銷這個右括號的放置。

決策樹的演示：

3.代碼編寫

class Solution {int left, right, n;string path;vector<string> ret;public:vector<string> generateParenthesis(int _n) {n = _n;dfs();return ret;}void dfs() {if (right == n) {ret.push_back(path);return;}if (left < n) // 添加左括號{path.push_back('(');left++;dfs();path.pop_back();left--; // 恢復現場}if (right < left) // 添加右括號{path.push_back(')');right++;dfs();path.pop_back();right--; // 恢復現場}}
};

The Last

嗯，就是這樣啦，文章到這里就結束啦，真心感謝你花時間來讀。

覺得有點收獲的話，不妨給我點個贊吧！

如果發現文章有啥漏洞或錯誤的地方，歡迎私信我或者在評論里提醒一聲~