符号三角形定义
如下图所示，符号三角形是由14个“+” 号和14个"-"号组成的符号三角形。两个同号下面都是“+” 号， 两个异号下面都是”-“。
在一般情况下， 符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n, 计算有多少
个不同的符号三角形，使其所含的"+ “和” - "的个数相同。
对于符号三角形问题，用n元组X[l:n]表示符号三角形的第一行的n个符号。
当x[i]=1 时，表示符号三角形的第一行的第t个符号为“+” ；当x[i]=0时，表示符号三角形的第一行的第t个号为"-"。
由于x[i]是
2值的， 所以在用回溯法解符号三角形问题时，可以用一棵完全二叉树来表示其解空间。
在符号三角形的第一行的前i个符号x[1:i]确定后， 就确定了一个由i*(i + 1)/2个符号组成的符号三角形。下一步确定x[i+l]的值后，只要在前面已确定的符号三角形的右边加一条边， 就可以扩展为x[1:i+l] 所相应的符号三角形。最终由x[l:n]所确定的符号三角形中包含的“+”个数与"-"个数同为n*(n+l)/4。
因此在回溯搜索过程中可用当前符号三角形所包含的“+”个数与"-"个数均不超过n*(n+l)/4 作为
可行性约束， 用于剪去不满足约束的子树。
对于给定的n, 当n*(n+l)/2 为奇数时， 显然不存在所包含的“+” 个数与"-"个数相同的符号三角形。这种情况可以通过简单的判断加以处理。
说明：
backtrack(level)：搜索解空间中第level层子树
主类的数据成员记录解空间中结点信息，以减少传给backtrack 的参数。
sum：记录当前已找到的“+”个数与"-"个数相同的符号三角形数。
在算法backtrack中， 当i>n时，算法搜索至叶结点， 得到一个新的"+“个数与”-"个数相同的符号三角形，当前已找到符号三角形数sum增l 。
当i<=n时， 当前扩展结点Z是解空间中的内部结点。该结点有x[i]=1 和x[i]=0共两个儿子结点。对当前扩展结点Z的每一个儿子结点， 计算其相应的符号三角形中“+”个数count与"-"个数，并以深度优先的方式递归地对可行子树搜索， 或剪去不可行子树。
public class Solution {
static int n; // 第一行符号个数
static int half; // n * (n+1) / 4 "+"/"-"符号个数
static int count; // 当前"+"个数
static int[][] p; // 符号三角形矩阵
static long sum; // 已找到的符号三角形数量
public static void main(String[] args) {
n = 4;
// n = 7;
count = 0;
sum = 0;
half = n * (n + 1) / 2; // 先初始化为符号三角形中的符号总个数
p = new int[n + 1][n + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
p[i][j] = 0;
}
}
System.out.println("不同的符号三角形分别为：");
compute(n);
System.out.println("首行" + n + "个符号且符合题目要求的一共有" + sum + "种不同的符号三角形");
// System.out.println("这" + sum + "种不同的符号三角形分别为：");
}
public static long compute(int firstCnt) {
if (half % 2 == 1) { // 符号总个数为奇数 不可能出现“+”、“-”个数相等的情况
return 0;
}
half /= 2; // 符号总个数为偶数 将 half设置为“+”(“-”)的个数
backtrack(1);
return sum;
}
private static void backtrack(int t) {
// 当前“+”或者“-”符号个数已经达到n * (n + 1) / 4
if ((count > half) || (t * (t - 1) / 2 - count > half)) {
return;
}
// TODO 已经构造出一个符合要求的符号三角形，数量加1
if (t > n) {
sum++;
// 打印符号三角形
for (int i = 1; i <= n; i++) {
for (int k = 1; k < i; k++) {
System.out.print(" ");
}
for (int j = 1; j <= n; j++) {
if (p[i][j] == 0 && j <= n - i + 1) {
System.out.print("+" + " ");
} else if (p[i][j] == 1 && j <= n - i + 1) {
System.out.print("-" + " ");
} else {
System.out.print(" ");
}
}
System.out.println();
}
System.out.println("----------------------------------");
} else {
// “+”、“-”用 0、1 代替（构造完全二叉树）
for (int i = 0; i < 2; i++) {
p[1][t] = i;
count += i;
// 上一行种只有大于等于2个符号才可以形成其下一行的一个符号
for (int j = 2; j <= t; j++) {
// TODO 通过异或的方式求其余行数的放置方式
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 j = 2; j <= t; j++) {
count -= p[j][t - j + 1];
}
count -= i;
}
}
}
}
运行结果
计算可行性约束需要O(n)时间，在最坏情况下有0(2n)个结点需要计算可行性约束，故解符号三角形问题的回溯算法backtrack所需的计算时间为O(n*2n)。
结束！