计蒜客：等边三角形（DFS）

相似题目： 正方形
蒜头君手上有一些小木棍，它们长短不一，蒜头君想用这些木棍拼出一个等边三角形，并且每根木棍都要用到。 例如，蒜头君手上有长度为 1，2，3，3 的4根木棍，他可以让长度为1，2 的木棍组成一条边，另外 2 跟分别组成 2 条边，拼成一个边长为 3 的等边三角形。蒜头君希望你提前告诉他能不能拼出来，免得白费功夫。

输入格式
首先输入一个整数 n(3≤n≤20)，表示木棍数量，接下来输入 n 根木棍的长度 pi (1≤ pi ≤10000)。

输出格式
如果蒜头君能拼出等边三角形，输出"yes"，否则输出"no"。

样例输入1

5
1 2 3 4 5

输出1

yes

样例输入2

4
1 1 1 1

输出2

no

题解1（能过9/10的测试点，会超时）：
一条边一条边的凑，如果能凑成，继续凑下一条边

#include<bits/stdc++.h>
using namespace std;
int n,sum;
bool f;
int p[10005];
bool vis[10005];
void dfs(int cnt,int s,int st){
    //cnt:当前已经凑齐了三角形的几条边，s:当前这条边的长度，st:以st号木棍为开始的情况，去除重复性，要不然最后会有k的阶乘的情况重复（总情况数要除以k的阶乘）
    if(f) return;
    if(cnt==3){
    
        f=true;
        return;
    }
    if(s==sum/3){
    //如果凑够了一条边，则凑下一条边
        dfs(cnt+1,0,0);
        return;
    }
    for(int i=0;i<n;i++){
    
        if(!vis[i]){
    
            vis[i]=true;
            dfs(cnt,s+p[i],i+1);
            vis[i]=false;
        }  
    }
}
int main(){
    
    cin>>n;
    for(int i=0;i<n;i++){
    
        cin>>p[i];
        sum+=p[i];
    }
    if(sum%3!=0){
    //特判：如果总和不能被3整除，说明肯定凑不来
        cout<<"no"<<endl;
        return 0;
    }
    dfs(0,0,0);
    if(f){
    
        cout<<"yes"<<endl;
    }else cout<<"no"<<endl;
    return 0;
}

题解2（优化后能ac）:
这道题目又是一道选择的题目，我们有三种选择的方法。
1：我们把这根木棍放到第一条边上。
2：我们把这根木棍放到第二条边上。
3：我们把这根木棍放到第三条边上。
对应三个dfs。与此同时处理好递归出口的问题就好了。
接下来我要说说这道题目的不同。我们对于这道题目我们可以进行一定的剪枝。
1：当平均值不是整数的时候我们就可以直接判定是无法拼成等边三角形的。
2：当其中的一个木棍长度大于平均值，也是无法拼成等边三角形的。
这个时候是不是发现其实优化也不是那么难？其实更多的优化都是我们自己可以想出来的，一个看似简单的优化，会给你的代码提高极大的运行效率。

#include<bits/stdc++.h>
using namespace std;
int n,sum;
int p[10005];
bool f;
void dfs(int a,int b,int c,int cnt){
    
    if(f) return;
    if(cnt>n) return;
    if(a>sum/3||b>sum/3||c>sum/3) return;
    if(cnt==n){
    
        if(a==sum/3&&b==sum/3&&c==sum/3){
    
            f=true;
        }
        return;
    }
    dfs(a+p[cnt],b,c,cnt+1);
    dfs(a,b+p[cnt],c,cnt+1);
    dfs(a,b,c+p[cnt],cnt+1);
}
int main(){
    
    cin>>n;
    for(int i=0;i<n;i++){
    
        cin>>p[i];
        sum+=p[i];
    }
    if(sum%3!=0){
    
        cout<<"no"<<endl;
        return 0;
    }
    dfs(0,0,0,0);
    if(f){
    
        cout<<"yes"<<endl;
    }else cout<<"no"<<endl;
    return 0;
}