题目：

 

题意：给你n个数，要你用光所有数字组成一个三角形，问能组成多少种不同的三角形

 

发现自己弱爆了。。。。Dfs（）超级弱。。。。

 

分析：每个数字一定在其中一条边，所以枚举所有数字的位置。。3^15暴搜，根本不需要什么used[]。。。

到所有数字都用完后，即到出口的时候，除去相同的三角形，重要的剪枝：a<=b<=c（看起来像没什么用，但是这是关键），且a,b,c都不等于0，

然后a + b*sum +c*sum*sum来构造一个唯一值再用set来计算总个数。。。。。

 

不要小看一些不起眼的剪枝。。。。

 

 

#include
     
          #include
      
           #include
       
            using namespace std;const int  M = 15 + 10;int save[M];int sum;int n;set <__int64> s;//64位void Dfs(int a, int b, int c, int num) {    if (num == n) {        if (a > b || b > c || a > c)//最关键的剪枝。。。保证a<=b<=c减少下面语句的执行次数        {            return ;        }                if (a && b && c && a + b > c)//保证不为0和能组成三角形        {        s.insert(a + b * sum + c * sum * sum);//构造唯一值        }        return;    }    Dfs(a + save[num + 1], b, c, num + 1);    Dfs(a , b + save[num + 1], c, num + 1);    Dfs(a , b, c + save[num + 1], num + 1);}int main() {    //freopen("in.txt", "r", stdin);    int t;    scanf("%d", &t);    while (t--) {        scanf("%d", &n);        sum = 0;        for (int i = 1; i <= n; i++) {            scanf("%d", save + i);            sum += save[i];        }        s.clear();        Dfs(0, 0, 0, 0);        printf("%d\n", s.size());    }    return 0;}