一、问题描述
在一般情况下，符号三角形第一行有N个符号，该问题要求对于给定n计算有多少种不同的符号三角形。使其所含的+ — 个数相同。
要求：n个符号 有多少个符号三角形(+- 个数相同、符合规则)
二、问题分析
(1)问题关键分析：对于一个符号三角形而言三角形面相分析，只要是第一行元素确定了，那么接下来整个符号三角形就确定了。因此，关键在于第一行的元素是怎么排列的？他能决定接下来的+-个数总和。
(2)对于确定第一行的元素排列三角形面相分析，+代表1，-代表0。由此想到二叉完全树(解空间情况)，进行回溯枚举。设n元组(eg 0 1 0 1 1 0以此来代表第一行元素的排列情况)
(3)大问题划分为小问题，找第i层问题与第i+1层问题的关系。因为第i个确定下来就代表这一个i个初始边的三角形确定了，那么i+1也是一个三角形，只是在以i个初始边的三角形多了一条。下一步确定x[i+1]的值后，只要在前面已确定的符号三角形的右边加一条边，就可以拓展为x[1:i+1]所对应的符号三角形。【此时就得判断它是否满足约束条件(即剪支！)】最终由x[1:n]所确定的符号三角形包含的“+”个数与“-”同为n(n+1)/4(n(n+1)/2的一半，也就是一半的符号)。
(4)确定出口情况。
(5)剪枝函数的确定。在回溯可将“+”、“-”个数均不超过n(n+1)/4为约束条件。同时，对于给定的n当n(n+1)/2为奇数时，显然不存在“+”和“-”个数相同的符号三角形。(因为奇数除以2有余数1，即+ - 个数不同。)
三、问题解决
int n = 0;
int sum = 0;
int half = n/2;
//+代表0 -代表1
void backtrack(int t)//确定解空间情况，设置n元组
{
int i , j;
if(t > n)//---确定出口
{
sum++;
//输出结果
}
for(int i = 0 ; i < 2 ; i++)//---枚举可能情况
{
//----转换前处理+实现约束条件
p[1][t] = i;//对第一行的t号元素赋值
counter += i;//-号的统计
for(int j = 2 ; j <= t ; ++j)//对-号进行统计
{
p[j][t-j+1] = p[j-1][t-j+1]^p[j-1][t-j+2];//对新增的最右边排的情况的填充
counter += p[j][t-j+1];//对该新增排 -号的统计
}
//---设置约束条件
if((counter <= half) && (t*(t+1)/2 - counter <= half))
{//第一个是-号数小于一半，第二个是+号数小于一半的要求
backtrack(t+1);
}
//---恢复现场
for(int j = 2 ; j <= t ; j++)
{
counter -= p[j][t-j+1];
}
counter -= i;
}
}
