回溯符号三角形

---

---

符号三角形中，有14个“+“和14个“-”。2个同号下面是+，两个异号下面是-。 在一般情况下，符号三角形的第一行有n个符号。符号三角形问题，要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”相同。
如图：

分析：

第一行安排好两个后，就可以根据第一行的两个，判断第二行的第一个；第一行的第3个安排好后，可以导出第二行第二个和第三行第一个。。。
　　就是这样的一个基本思路
注意：
　　if(cut<=half && ((t+1)*t/2-cut)<=half)原本加到了外层，但是结果总出现6（n=7时，正确结果为12），把判断条件挪到了里面就OK了
　　因为，判断条件放外层，当‘+’和‘-’的个数小于等于half时，都能进入，但不要忘了，内层的操作会增加‘+’和‘-’的个数。就会存在外层小于half，内层一系列操作后，个数大于half的情况，而通过题目知道，这种情况是不应该发生的，所以导致了最终结果不正确。

代码：

#include<stdio.h>
#define n 7            //第一行的n个符号 ，也代表n行 
int half,cut=0; //cut是减号的数量 
int count=0;//方案数量
int p[n+1][n+1];  
 
void traceback(int t){
    if(t>n){     //第一行的n个符号全部安排好了 
        count++;
        return; 
    } 
    for(int i=0;i<2;i++){  //0代表加号，1代表减号
        p[1][t]=i;
        cut+=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];   //无非是对坐标出来的  
            cut+=p[j][t-j+1]; 
        }
        if(cut<=half && ((t+1)*t/2-cut)<=half){
            traceback(t+1);
        }
        for(int j=2;j<=t;j++)
            cut-=p[j][t-j+1];
        cut-=i;
    }   
}   

int main(){
    if(((n+1)*n/2)%2==1)                    //当n是5的时候，（5+1）*5/2=15（15是加号和减号的总数）。15/2=7.5, 
        printf("the answer is 0");          //表示7.5个'+'，7.5个'-',显然不符合要求
    half=((n+1)*n/2)/2;    //加号、减号各half个
    traceback(1);          //t代表第一行的第几个符号，因为第一行确定几个符号，下面相应的确定几行 
    printf("%d\n",count); 
    return 0;
}

运行截图