1.题目呈现

逗志芃在干了很多事情后终于闲下来了，然后就陷入了深深的无聊中。不过他想到了一个游戏来使他更无聊。他拿出n个木棍，然后选出其中一些粘成一根长的，然后再选一些粘成另一个长的，他想知道在两根一样长的情况下长度最长是多少。

输入格式

　　第一行一个数n，表示n个棍子。第二行n个数，每个数表示一根棍子的长度。

输出格式

　　一个数，最大的长度。

样例输入

4
1 2 3 1

样例输出

3

数据规模和约定

n<=15

2.思路探究

1).初步思想

不难看出这道题是一道非常经典的状态搜索的题目

根据对搜索类题目一种潜意识(可能是我做的题比较少)，我的第一反应是使用暴力推导(虽然可能不能得全部的分数，但也是最保底的一种情况)，在看到数据规模和约定时，我便更加坚定了我的想法,(n<=15它再怎么大也不可能超时的)

所以我们便大胆的开始暴力！

举个栗子：1 2 3 1

我们列出所有以上四位数的可能性

比如(只从1开始)：1 1+2=3 1+3=4 1+2+3=6 1+1=2 1+2+3+1=7

列出所有的情况，是 16 个情况

下面就是状态搜索的情况了哦

根据题意，我们直到逗先生他所拿拼接的两个长木棒是不存在重复的火柴棒的，所以我们在后期搜索的过程中，要排除掉两个长木棒中含有相同的木棒的情况！

例如：第一根长棒1+3=4

           第二根长棒3+1=4

我们可以看到，3重复了，所以我们需要抛弃这个情况

我们维护一个max变量

如果两个长棒中没有相同的小火柴且两个长棒的重量相等，我们与max相比较，如果比max大，则替换掉max的数值！

2).具体实现

有了思路，我们如何具体的解决呢

我们当前有个非常棘手的问题就是如何来表示一个长木棒中都有哪几个木棒呢

在这里我们可以采用二进制位运算的形式来表示

还是这个例子 1 2 3 1

我们设0000是 长棒中没有木棒 0011指的是长棒中有一号和二号的木棒，一直到1111

总共是16中情况，也就是2^n

所以我们便使用二进制来保存长棒中含有的木棒

忘记了位运算的同学去看一下位运算哈

3.代码实现

#include <iostream>

using namespace std; 

int a[100001];
int b[100001];

int main(){
	int n;
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> a[i];
	}
	for(int i=0;i<(1<<n);i++){//1<<n指的是2^n 指的是n的二进制的排列的所有的情况 
		for(int j=0;j<n;j++){
			if(i&(1<<j)) b[i]+=a[j];//1<<j表示将1推到第j位，i&(1<<j)表示，看第j根火柴在不在第i种情况中，若在，则重量相加 
		}
	}
	int maxnum = -1;
	for(int i=0;i<(1<<n);i++){
		for(int j=0;j<(1<<n);j++)
		   if(!(i&j)&&b[i]==b[j]) maxnum=max(maxnum,b[i]);//若i,j中不包含相同的火柴，且他们两个的长度相等，则与max比较 
	}
	cout << maxnum;
	return 0;
}