问题描述
逗志芃在干了很多事情后终于闲下来了，然后就陷入了深深的无聊中。不过他想到了一个游戏来使他更无聊。他拿出n个木棍，然后选出其中一些粘成一根长的，然后再选一些粘成另一个长的，他想知道在两根一样长的情况下长度最长是多少。
输入格式
第一行一个数n，表示n个棍子。第二行n个数，每个数表示一根棍子的长度。
输出格式
一个数，最大的长度。

光看题感觉挺简单的，标签给的状态搜索，蒟蒻的我不知道是什么。想的直接就是暴力

上代码！

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll n;
ll a[20];
int sign[20];
ll ans;
void dfs(ll sum1,ll sum2)
{
	ll i;
	for(i=1;i<=n;i++)
	{
		if(sum1==sum2)
		{
			ans=max(ans,sum1);
		}
		if(sign[i]==0&&sum1<=sum2)
		{
			sign[i]=1;
			dfs(sum1+a[i],sum2);
			sign[i]=0;
		}
		if(sign[i]==0&&sum1>=sum2){
			sign[i]=1;
			dfs(sum1,sum2+a[i]);
			sign[i]=0;
		}
	}
}
int main()
{
	ll i;
	cin>>n;
	for(i=1;i<=n;i++)
		cin>>a[i];
	dfs(0,0);
	cout<<ans;
 } 

我giao，一个测试点都没过，全超时。   测试点n都是15
我这个代码一定会走到最坏情况，因为没有任何return命令，dfs最坏情况是!n，而我调用了两次差不多是2!n
大概执行了2.615348736e+12次 =.=  emm~

附一张算法竞赛复杂度考虑图片，以后dfs不return  看见10直接略过了
有时间整理一期比较完整的算法竞赛复杂度考虑的文章

还是看看大佬的代码吧https://blog.csdn.net/TheMARKZERO/article/details/122373846

用的递推公式

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> v;
    for(int i=0;i<n;i++){
        int num;
        cin>>num;
        v.push_back(num);
    }
    vector<int> v2((1<<n));
    for(int i=0;i<(1<<n);i++){//(1<<n)即2^n
        for(int j=0;j<n;j++){//有n根木棒
            if(i&(1<<j)){//说明这个状态有这根木棒
                v2[i]+=v[j];
            }
        }
    }
    int result=0;
    //组合之间进行比较
    for(int i=0;i<(1<<n);i++){//(1<<n)即2^n
        for(int j=0;j<(1<<n);j++){//(1<<n)即2^n
            if(!(i&j)&&v2[i]==v2[j]){//状态不同但是值相同 !(i&j)是为了判断两个组合中是否包含相同的木棒，如果包含相同的木棒，
                                     //那么值不会是0
                result=max(result,v2[i]);
            }
        }
    }
    cout<<result;
    return 0;
}