题目大意：有N个木棒，相互组合拼接，能组成多少种不同的三角形。

思路：假设c>=b>=a 然后枚举C，在C的dfs里嵌套枚举B的DFS。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#define mod 2000007

using  namespace std;

int n;

int X[20];

bool vis[20];

int ans;

long long sum;

long long hash[mod];

bool ok(int b,int c)

{

    int a=sum-b-c;

    if(a+b>c && c>=b && b>=a)return true;

    return false;

}

bool work(long long t)

{

    int v=t%mod;

    while(hash[v]!=t && hash[v]!=-1)//.....之前这里写成了IF  卡了半天再找到。以后要细心。。。

    v=(v+10)%mod;

    if(hash[v]==-1)

    {

        hash[v]=t;

        return true;

    }

    return false;

}

void dfsb(int pos,int c,int b)

{

    //printf("c = %d b = %d\n",c,b);

    for(int i=pos;i<=n;i++)

    {

        if(vis[i])continue;

        vis[i]=true;

        b+=X[i];

        if(ok(b,c))

        {

            //printf("c = %d,b = %d,a = %d\n",c,b,sum-b-c);

            int a=sum-b-c;

            long long t=(long long)a+(long long)b*sum+(long long)c*sum*sum;

            if(work(t))ans++;

        }

        if(b<=c)dfsb(i,c,b);

        b-=X[i];

        vis[i]=false;

    }

}

void dfsc(int pos,int c)

{

    for(int i=pos;i<=n;i++)

    {

        if(vis[i])continue;

        vis[i]=true;

        c+=X[i];

        if(c>=sum/3 && c<=sum/2)dfsb(1,c,0);//剪枝

        dfsc(i,c);

        c-=X[i];

        vis[i]=false;

    }

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        memset(vis,0,sizeof(vis));

        memset(hash,-1,sizeof(hash));

        sum=0;

        for(int i=1;i<=n;i++)

        {

            scanf("%d",&X[i]);

            sum+=X[i];

        }

        ans=0;

        dfsc(1,0);

        printf("%d\n",ans);

    }

    return 0;

}