如何通过回溯算法生成所有括号组合？
摘要：📘 回溯法：生成合法括号组合（n 对） 🧩 功能说明 这段代码的功能是：输入一个整数 n，输出所有可能的 n 对合法括号组合。 合法括号组合的定义是：括号必须成对匹配、顺序合理
📘 回溯法：生成合法括号组合（n 对）
🧩 功能说明
这段代码的功能是：输入一个整数 n，输出所有可能的 n 对合法括号组合。
合法括号组合的定义是：括号必须成对匹配、顺序合理，不能出现像 ())( 这样的无效形式。
🧠 核心算法：回溯法（Backtracking）
通过递归地尝试每一个可能的分支选择（放左括号或右括号），构造出所有合法的组合路径。
🔍 类定义和主函数结构
#include <iostream>
#include <vector>
#include <climits>
#include <cmath>
#include <unordered_set>
using namespace std;
class Solution
{
public:
vector<string> res;
void backtrack(int n, int left, int right, string &temp)
{
if (left == n && right == n)
{
res.push_back(temp);
return;
}
if (left < n)
{
temp += '(';
backtarck(n, left + 1, right, temp);
temp.pop_back();
}
if (left > right)
{
temp += ')';
backtarck(n, left, right + 1, temp);
temp.pop_back();
}
}
};
int main(int argc, char const *argv[])
{
Solution solution;
int n;
cin >> n;
string temp;
solution.backtrack(n, 0, 0, temp);
for (string s : solution.res)
{
cout << s << '\n';
}
return 0;
}
🧱 回溯逻辑详解（3 个 if 条件）
✅ 1. if (left == n && right == n)
含义：左右括号都已放满，构造完成。
作用：将当前字符串 temp 加入结果。
注意：必须放在最前面，作为递归终止条件。
✅ 2. if (left < n)
含义：左括号还没放满，可以尝试放 '('。
递归前：temp += '('
递归后：temp.pop_back() 回退操作
✅ 3. if (left > right)
含义：当前已有多余的左括号，可以安全地放一个右括号。
保证：括号不会不合法（比如 ())）。
递归逻辑与左括号类似。
🔄 条件顺序是否可以交换？
if (left == n && right == n) 必须在最前，作为终止条件。
left < n 和 left > right 是并行探索路径，可以交换顺序，不影响最终结果，只影响输出的排列顺序。