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;
            }
        }
    }
}