对于符号三角形问题,用n元组x[1：n]表示符号三角形的第一行的n个符号.当x[i]=1时,表示符号三角形的第一行的第i个符号为“+”号；当x[i]=0时,表示符号三角形的第一行的第i个符号为“-”号；1 ≤ i≤ n.由于x[i]是二值的,所以在用回溯法解符号三角形问题时,可以用一棵完全二叉树来表示其解空间.在符号三角形的第一行的前i个符号x[1：i ]确定后,就确定了一个由i*（i+1）/2个符号组成的符号三角形.下一步确定了x[i+1]的值后,只要在前面已确定的符号三角形的右边加一条边,就可以扩展为x[1：i+1]所相应的符号三角形.最终由x[1：n]所确定的符号三角形中包含的“+”号个数与“-”号个数同为n*（n+1）/4.因此在回溯搜索过程中可用当前符号三角形所包含的“+”号个数与“-”号个数均不超过n*（n+1）/4作为可行性约束,用于剪去不满足约束的子树.
另外,对于给定的n,当n*（n+1）/2为奇数时,显然不存在所包含的“+”号个数与“-”号个数相同的符号三角形.
转自http://hi.baidu.com/fandywang%5Fjlu/blog/item/61a9b98bc48a64d5fd1f108a.html