力扣 22. 括号生成：C++ 实现回溯 + 动态规划双解法，面试高频题必掌握
在算法面试中，括号生成问题是经典的字符串组合题型，力扣第 22 题「括号生成」更是高频考点。题目要求给定括号对数 n，生成所有有效的括号组合，看似简单却能深度考察对回溯、动态规划等核心算法思想的掌握。今天用 C++ 实现两种最优解法，兼顾代码简洁性和可读性，小白也能轻松理解！
一、题目核心分析
- 输入：括号对数 n（1≤n≤8）
- 输出：所有有效括号组合（有效 = 左右括号数量相等 + 每一步左括号数≥右括号数）
- 示例：n=3 时，输出 ["((()))","(()())","(())()","()(())","()()()"]
关键约束：生成过程中必须保证「左括号未用完时可加左括号，右括号数量小于左括号时可加右括号」，这是避免无效组合的核心。
二、解法一：回溯算法（最优解）
回溯本质是「试探 - 回退」的深度优先搜索，通过剪枝避免无效路径，效率极高，也是 C++ 面试中最推荐的写法。
核心思路
- 定义辅助递归函数，参数包含当前组合字符串、左括号使用数、右括号使用数和结果集（引用传递）。
- 终止条件：左右括号均用完（字符串长度 = 2n），将当前组合加入结果集。
- 剪枝逻辑：
- 左括号未用完（left < n）：可添加左括号，递归继续。
- 右括号少于左括号（right < left）：可添加右括号，递归继续。
代码实现（C++）
#include <vector> #include <string> using namespace std; class Solution { public: vector<string> generateParenthesis(int n) { vector<string> result; backtrack("", 0, 0, n, result); return result; } private: // 回溯函数：当前字符串、左括号数、右括号数、总对数、结果集 void backtrack(string current, int left, int right, int n, vector<string>& result) { // 终止条件：字符串长度达到2n（左右括号均用完） if (current.size() == 2 * n) { result.push_back(current); return; } // 左括号未用完，可添加左括号 if (left < n) { backtrack(current + '(', left + 1, right, n, result); } // 右括号数量小于左括号，可添加右括号（保证有效） if (right < left) { backtrack(current + ')', left, right + 1, n, result); } } };优势
- 时间复杂度 O (4ⁿ/√n)：符合卡特兰数时间规模，无多余无效路径。
- 空间复杂度 O (n)：递归栈深度最多为 2n，额外空间仅用于存储结果。
- C++ 特性适配：通过引用传递 result 避免拷贝开销，string 拼接高效简洁。
三、解法二：动态规划（递推思想）
通过拆解子问题，利用已解决的 n-1 对括号组合推导 n 对的结果，适合喜欢递推思路的同学，C++ 中 vector 的嵌套存储让子问题结果复用更方便。
核心思路
- 状态定义：dp [i] 表示 i 对括号的所有有效组合（vector<string>类型）。
- 递推公式：dp [i] = "(" + dp [p] + ")" + dp [q]，其中 p+q = i-1（p≥0，q≥0）。
- 解释：每新增 1 对括号，可视为在 p 对括号外包裹 1 对括号，再拼接 q 对括号。
- 初始状态：dp [0] = {""}（0 对括号对应空字符串）。
代码实现（C++）
#include <vector> #include <string> using namespace std; class Solution { public: vector<string> generateParenthesis(int n) { // dp[i]存储i对括号的所有有效组合 vector<vector<string>> dp(n + 1); dp[0] = {""}; // 初始状态：0对括号为空字符串 // 递推计算1到n对括号的组合 for (int i = 1; i <= n; ++i) { // 遍历所有可能的p（q = i-1 - p） for (int p = 0; p < i; ++p) { int q = i - 1 - p; // 拼接所有p和q的组合 for (const string& strP : dp[p]) { for (const string& strQ : dp[q]) { dp[i].push_back("(" + strP + ")" + strQ); } } } } return dp[n]; } };优势
- 逻辑直观：通过子问题拼接得到结果，无需递归，避免栈溢出风险。
- 可复用性强：dp 数组存储了所有小于 n 的结果，便于后续扩展（如统计组合数、筛选特定格式组合）。
- C++ 容器适配：vector 的动态扩容特性完美适配不同规模的结果存储。
四、两种解法对比与实战建议
| 解法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 回溯算法 | O(4ⁿ/√n) | O(n) | 面试首选（代码简洁） |
| 动态规划 | O(4ⁿ/√n) | O(4ⁿ/√n) | 需复用子问题结果时 |
实战建议：
- 面试中优先写回溯算法，C++ 代码仅需一个辅助函数，逻辑清晰易解释。
- 若面试官追问非递归解法或优化方向，再补充动态规划思路。
- 核心约束「左括号数≥右括号数」是有效组合的关键，务必牢记。
- 代码可直接运行：包含必要头文件和类结构，LeetCode 提交即可通过。
五、总结
括号生成问题的核心是「有效约束」和「组合遍历」，C++ 实现中，回溯算法利用递归 + 剪枝高效筛选路径，动态规划借助 vector 容器实现子问题递推。两种解法均围绕卡特兰数的数学本质，掌握后可举一反三解决同类组合问题（如合法括号计数、括号匹配检查等）。
建议先手动模拟 n=2、n=3 的生成过程，再对照代码理解逻辑，最后自己动手实现一遍。如果有优化思路或其他解法，欢迎在评论区交流～