下面都是“-”。 下图是由14个“+”和14个“-”组成的符号三角形。2个同号下面都是“+”，2个异号下面都是“-”。 在一般情况下，符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。
#include<iostream> using namespace std; class Triangle{ friend int Compute(int); private: void Backtrack(int t); int n, half, count, **p; long sum; }; void Triangle::Backtrack(int t){ if((count>half)||(t*(t-1)/2-count>half)) return; if(t>n) sum++; else for(int i=0;i<2;i++){ p[1][t]=i; count+=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]; count+=p[j][t-j+1]; } Backtrack(t+1); for(int k=2;k<=t;k++) count-=p[k][t-k+1]; count-=i; } } int Compute(int n){ Triangle X; X.n=n; X.count=0; X.sum=0; X.half=n*(n+1)/2; if(X.half%2==1) return 0; X.half=X.half/2; int **p=new int *[n+1]; for(int i=0;i<=n;i++) p[i]=new int [n+1]; for(int k=0;k<=n;k++) for(int j=0;j<=n;j++) p[k][j]=0; X.p=p; X.Backtrack(1); return X.sum; } void main(){ int n,t; cin>>n; t=Compute(n); cout<<t<<endl; }