符号三角形问题第一次见到时有点唬人：第一行给出 n 个 + 和 -，然后看相邻两个符号是相同还是不同，在下一行对应位置生成 + 或 -，一层层往下，直到只剩一个符号。实际上它是个计数问题，不是模拟问题——要算的是：有多少种第一行布局，能让整个三角形里 + 和 - 的数量正好相等。用回溯法枚举第一行的每一种可能，再加上关键剪枝，是这个问题的标准解法，也是理解回溯法“如何增量更新状态、如何在递归途中提前砍掉无效分支”的绝佳案例。
这篇文章会从数学建模开始，逐步拆解回溯的搜索顺序、三角形状态的增量更新方法、剪枝条件的推导，然后给出可以直接运行的 C++ 代码，最后记录一些我实际调试中踩过的坑。不管你是刚学回溯法，还是在准备算法面试，只要照着思路走一遍，符号三角形这类“构造 + 计数”问题基本就能举一反三。
1. 问题建模：先把三角形的数学规则讲清楚
1.1 符号三角形的生成规则
先约定一下符号位置。第一行有 n 个符号，编号从 1 到 n；第二行有 n-1 个，第三行有 n-2 个，直到第 n 行只有 1 个。也就是说第 i 行有 n-i+1 个符号。
生成规则只有一句话：
- 如果上一层相邻两个符号相同，则下一行对应位置为 +；
- 如果上一层相邻两个符号不同，则下一行对应位置为 -。
举例来说，n = 3 时，如果第一行是：
+ + -第二行就是：
+ -因为前两个 + 相同，所以第二行第一个是 +；后两个一个是 + 一个是 -，不同，所以第二行第二个是 -。第三行再根据第二行的 “+” 和 “-” 生成，因为它们不同，所以第三行是：
-整个三角形的符号总数是：
total = n + (n-1) + ... + 1 = n * (n + 1) / 2这是问题里最容易被忽略的数学基础。后面所有剪枝和判断都依赖这个总和。
1.2 用 0/1 和异或描述规则
写代码时直接用字符比较也可以，但更优雅的做法是把 + 和 - 映射成 0 和 1，然后用异或表达。
假设用 0 表示 +，用 1 表示 -，那么“上下两个符号是否相同”就可以这样判断：
p[i][j] = p[i-1][j] ^ p[i-1][j+1]异或的结果正好是：
- 两个符号相同：0，表示 +；
- 两个符号不同：1，表示 -。
也就是说，整个三角形的生成可以完全由第一行决定。第一行一旦确定，下面每一行都是上一层相邻两个元素的异或结果。这不只是简化写代码，更重要的是它让“状态更新”变得非常直接。
1.3 问题本质：在 2^n 个候选中计数
这个问题的目标是让三角形里的 + 和 - 数量相等。把符号转换成 0/1 后，就是让 0 的数量等于 1 的数量，都等于 total 的一半。
所以第一个结论是：
如果 total 是奇数，直接输出 0，不需要搜索。
因为总数都没法平分，更不可能存在合法三角形。
第一行每个位置只有两种选择，所以候选空间是 2^n。n 比较小的时候，直接枚举所有第一行、再生成完整三角形，似乎也能做出来；但当 n 到 20 以上，每增加一列，候选数量就翻一倍。回溯法的价值就在这里：它不是等第一行全部填完再去验，而是每填一个符号就立刻检查当前部分三角形有没有可能达到平衡，不可能就立刻回头。
2. 回溯法为什么是首选方案
2.1 决策变量与搜索顺序
回溯法解题，第一步永远是确定“决策变量”。在这个问题里，第一行 n 个位置就是决策变量，每个位置选 0 或 1。只要第一行确定了，三角形就确定了，所以完全不需要枚举中间行。
搜索顺序也很关键。常见做法是从左到右，一个一个确定第一行的符号。这里有一个很容易忽略的点：当确定第一行第 t 个符号后，并不只是第一行多了一个符号，而是整条“新斜线”都可以立刻确定。
比如已经确定了第一行前三个符号 a、b、c，那么局部三角形是：
a b c a^b b^c a^b^b^c = a^c注意第三行的斜线位置也能算出来。当继续填入第四符号 d 时，新产生的符号是：
第2行第3个 = c ^ d 第3行第2个 = (b ^ c) ^ (c ^ d) = b ^ d 第4行第1个 = (a ^ c) ^ (b ^ d)这正好构成一条新的右下斜线。换句话说，每填一个第一行符号，当前已知的三角形就多了一整条斜线，从第 1 行一直延伸到第 t 行。这就是增量更新的核心。
2.2 剪枝条件是怎么来的
记当前已经生成的符号数为：
gen = k * (k + 1) / 2其中 k 是已经确定的第一行符号个数。用一个变量 cnt1 记录当前三角形中“1”的个数，那么“0”的个数就是：
cnt0 = gen - cnt1剪枝条件主要有两个。
第一个是最直观的：如果 cnt1 已经大于 half，或者 cnt0 已经大于 half，那后面无论怎么填都不可能平衡。因为最终要的是 1 和 0 各占一半，现在某一方已经超了，剩下符号全给另一方也补不回来。
第二个稍微强一点：考虑剩余符号数：
remain = total - gen就算剩下的符号全部都是 1，也不能让 cnt1 达到 half，即：
cnt1 + remain < half那这个分支也不可能成功。同理：
cnt0 + remain < half也可以剪掉。这个剪枝比第一个更细一点，尤其在搜索到中后段时，能明显减少无效递归。
2.3 一个容易误入的“对称优化”
我第一次做这道题时，第一反应是“把 + 和 - 全部互换，三角形应该还是合法的，所以固定第一个符号，最后答案乘 2 就行”。这个直觉在这个规则下是不成立的，而且很容易让人白改半天。
原因是这样的：如果用 0/1 表示符号，生成规则是异或：
p[i][j] = p[i-1][j] ^ p[i-1][j+1]如果把第一行所有符号都取反，那么：
(1 - x) ^ (1 - y) = x ^ y也就是说，下一行的值完全不变，而不是跟着取反。所以全局取反不会把合法三角形映射成另一个合法三角形。换句话说，这个问题没有“首字符固定后翻倍”的对称性。别在这上面浪费时间。
3. 代码实现与关键细节拆解
3.1 数据结构与核心变量
代码里需要这几样东西：
int p[MAXN][MAXN]：存整个三角形，0/1；int cnt1：当前已生成三角形中“1”的个数；int total和half：符号总数和平衡目标；int ans：统计合法方案数。
p数组开大一点，比如MAXN = 30，因为 n 通常在 20 到 25 这个范围。回调和搜索深度都只有 n，不会爆栈。
3.2 回溯函数的增量更新逻辑
核心函数是dfs(k)，表示第一行已经确定了前 k 个符号。每次进入函数，先根据cnt1判断剪枝条件。如果还能继续，就枚举第 k+1 个符号是 0 还是 1。
关键在更新部分。假设当前要放第一行第 t 个符号：
t = k + 1先写：
p[1][t] = bit;然后从第 2 行开始，一直更新到第 t 行：
for (int i = 2; i <= t; ++i) { p[i][t - i + 1] = p[i - 1][t - i + 1] ^ p[i - 1][t - i + 2]; }这里的坐标很多人第一眼会犯晕。我建议把下标代入一个小例子验证：t = 3 时，i = 2 算的是：
p[2][2] = p[1][2] ^ p[1][3]i = 3 算的是：
p[3][1] = p[2][1] ^ p[2][2]p[2][1]在之前已经算好，p[2][2]是刚算出来的，所以顺序不能反。这个循环本质上就是沿着新斜线从左上方往右下方“滚”下来。
新产生了一串符号位，把它们全部累加到一个delta变量里：
int delta = bit; for (...) { delta += p[i][t - i + 1]; } cnt1 += delta; dfs(t); cnt1 -= delta;递归回来后减去delta，这是回溯法撤销状态的经典操作。p数组本身不需要恢复，因为每个位置在被读取前，一定会被后续某条新斜线重新覆盖。
3.3 完整可运行的参考代码
下面这份代码可以直接编译运行，输入一个整数 n，输出满足条件的三角形数量。
#include <bits/stdc++.h> using namespace std; const int MAXN = 30; int n, total, half, ans; int p[MAXN][MAXN]; int cnt1; void dfs(int k) { // 当前第一行已经确定前 k 个符号 int gen = k * (k + 1) / 2; int cnt0 = gen - cnt1; // 剪枝条件1：某一方数量已经超过一半 if (cnt1 > half || cnt0 > half) return; // 剪枝条件2：剩余符号全部给某一方也追不上 half int remain = total - gen; if (cnt1 + remain < half || cnt0 + remain < half) return; // 第一行全部填完，产生一个合法三角形 if (k == n) { ++ans; return; } // 尝试第一行第 k+1 个符号 int t = k + 1; for (int bit = 0; bit <= 1; ++bit) { p[1][t] = bit; int delta = bit; // 沿新斜线更新三角形 for (int i = 2; i <= t; ++i) { p[i][t - i + 1] = p[i - 1][t - i + 1] ^ p[i - 1][t - i + 2]; delta += p[i][t - i + 1]; } cnt1 += delta; dfs(t); cnt1 -= delta; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; total = n * (n + 1) / 2; if (total & 1) { cout << 0 << '\n'; return 0; } half = total / 2; dfs(0); cout << ans << '\n'; return 0; }代码里dfs(0)表示一个符号都还没放。第一次进入函数时gen = 0，剪枝自然放行，然后枚举第一行第一个符号。这里没有做任何“对称加倍”，因为前面说过，在这个问题里那样做是错的。
3.4 如果想输出全部三角形
有些题目不是只计数，而是要求打印所有合法三角形。那只需要在k == n的位置调用一个打印函数：
void printTriangle() { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n - i + 1; ++j) { cout << (p[i][j] ? '-' : '+'); } cout << '\n'; } cout << '\n'; }在dfs的终止分支里先printTriangle()，再++ans就行。注意打印时p数组保存的正是当前解，所以必须在递归返回前直接打印，不要收集到容器里再等回溯结束后使用，因为回溯会覆盖这些位置。
4. 性能表现与进一步优化
4.1 剪枝带来的实际收益
回溯法最核心的收益不是“枚举更快”，而是“提前知道这条路走不通”。
如果完全没有剪枝，那么就是遍历完整的 2^n 个叶子节点。每到一个叶子，还要重新把整个三角形生成一遍，代价是 O(n^2)，所以总复杂度是 O(2^n * n^2)。这在 n 超过 20 后会变得非常难受。
加上剪枝之后，很多分支在第一行填到一半时就会被砍掉。尤其cnt1 > half || cnt0 > half这个条件，配合remain剪枝，能让无效子树根本来不及展开。
从实际测试来看，n = 18 到 n = 20 这个范围，回溯加剪枝基本都是毫秒级到亚秒级。n 到 23、24 附近，运行时间会明显上升；这是搜索空间本身的指数特性决定的，不是代码结构有问题。
4.2 更进一步的优化方向
如果题目给的 n 比较大，可以做几件小事：
- 把三角的行状态压成整数。异或天然适合位运算，每一行的下一行可以用整行的异或移位快速算出，再用内置的
__builtin_popcount统计新增符号个数。不过边界掩码和回溯时计数恢复会比较绕，适合想挑战一下写法的读者。 - 分支顺序可以稍微调整。比如当前 cnt1 比较小的时候，优先尝试放 bit = 0？还是优先放会让某一方迅速超限的 bit？这个对最终答案没有影响，但会影响剪枝触发的早晚。想压时间的话可以试着做一点“启发式排序”。
- 先判断
total奇偶。这能直接过滤掉一半的 n，而且逻辑上完全不会漏解。
4.3 什么情况下会超时
如果 n 到 25 以上，普通回溯基本就会吃力。即使剪枝很强，最坏情况下的合法三角形数量仍然可能非常大，每个合法叶子都要走到。如果真的遇到超大 n，需要重新找更强的数学模型，而不只是靠回溯硬跑。
不过经典算法题里，符号三角形通常把 n 控制在 20 左右。换句话说，上面这份代码在通常题目范围内已经够用，不需要一上来就搞各种复杂优化。
5. 常见问题与排查技巧实录
5.1 症状与原因对照表
调试这类回溯题，很多 bug 是“看着代码很对，但答案就是不对”。下面整理一份常见的排查表：
| 症状 | 常见原因 | 处理办法 |
|---|---|---|
| 输出 0，但手算明明有解 | 没有判断total奇偶，或者剪枝条件把等号写成了>= | half只有在 total 为偶数时才有意义；中间状态计数等于 half 时不能剪，要用>而不是>= |
| 答案偏小 | 以为取反后对称，固定第一个符号后乘 2 | 直接枚举全部第一行，不要做这个对称优化 |
| 答案偏大 | 回溯后忘记cnt1 -= delta | 每次递归调用后必须把cnt1恢复；建议在dfs里用delta局部变量统一加减 |
| 生成的三角形结构错误 | 斜线更新的下标写反 | 用 n=3 手推一遍，确认p[i][t-i+1]依赖的是p[i-1][t-i+1] ^ p[i-1][t-i+2] |
| 运行时间很长 | 只剪了cnt1 > half，没有用remain剪枝 | 加上cnt1 + remain < half和cnt0 + remain < half |
| 打印的解全部一样 | 回溯时打印了同一个p数组的旧内容 | 在k == n分支内直接打印，不要在回溯后统一打印 |
5.2 调试建议
我调试这类题时有一个固定套路：先用很小的 n 验证正确性，再考虑性能。
比如 n = 3 时，第一行只有 8 种可能，手算可以得到 4 个合法三角形。代码跑出来也应该输出 4。如果这个值不对，优先检查更新斜线的下标公式，其次是剪枝的等号问题。
等小规模正确后，再逐步加大 n，观察时间增长趋势。如果 n 从 18 加到 19，时间接近翻倍，说明剪枝可能没有完全生效；如果增长平缓，说明大部分无效分支都被提前砍掉了。
另外一个经常被忽略的点是：p数组是共用状态，递归进入下一层前写入的数据，在返回后不会自动消失。这个设计是故意的，但如果你在某处提前读取了还没更新的位置，就会读到旧值。排查时可以在关键位置打印cnt1、gen和刚刚算出的斜线值，很容易看出是不是更新顺序错了。
我的个人体会是，符号三角形这个问题的思维难点不在“回溯”本身，而在于“如何把一个二维三角结构的生成拆成一层层的增量更新”。只要把新斜线和剪枝条件想明白，代码本身非常短。以后再遇到那种“每一步都会连带产生多个新状态”的问题，就能直接套用同样的思路：把状态增量想清楚，再用剩余量做剪枝。
