给定N（N<=35)个数字，每个数字都<= 2^15. 其中一个或多个数字加和可以得到s，求出s的绝对值的最小值，并给出当s取绝对值最小值时，需要加和的数字的个数。
需要枚举集合的所有情况，2^35，会超时。考虑使用折半枚举的方法，考虑前 N/2个数字构成的集合S1，在S1中进行所有情况枚举，复杂度为 2^17，并将所有可能的和sum以及构成和sum需要的数字个数count存放在map M中；然后在S2中进行所有情况的枚举，复杂度为2^17，对于每种情况的sum2，在M中查找 -sum2的位置，在该位置前后位置处进行查找，求和的最小值。
还需要考虑，当s只有S1中的数字构成或者s只有S2中的数字构成，或者s由S1和S2中的数字构成的三类情况。
总的时间复杂度为 O(2^17 + 2^17*log(2^17)) = O(2^22)
这道题wrong answer了20次，我操！最后发现最开始的 min_sum 设置为 2^20 出了问题，如果设为 an[0]（集合S中的第一个数）就ok，仍然不知道为何！
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<cmath>
#include<iostream>
#include<map>
using namespace std;
long long int ll_abs(long long int n){
if (n >= 0)
return n;
return -n;
}
long long int an[40];
map<long long int, int> sum_map;
int main2(){
int n;
while (scanf("%d", &n) && n){
map<long long int, int>::iterator it;
sum_map.clear();
for (int i = 0; i < n; i++){
scanf("%lld", &an[i]);
}
long long int min_sum = ll_abs(an[0]);
int min_count = 1;
int m = n / 2;
for (int i = 0; m > 0 && i < (1 << m); i++){
long long int sum = 0;
int count = 0;
int t = i;
for (int k = 0; k < m; k++){
if (t & 1){
sum += an[k];
count++;
}
t >>= 1;
}
if (count == 0)
continue;
if (sum_map.find(sum) != sum_map.end()){
sum_map[sum] = min(sum_map[sum], count);
}
else
sum_map[sum] = count;
if (ll_abs(sum) < min_sum){
min_sum = ll_abs(sum);
min_count = count;
}
else if (ll_abs(sum) == min_sum){
min_count = min(min_count, count);
}
}
m = n / 2 + n % 2;
for (int i = 0; i < (1 << m); i++){
long long int sum = 0;
int count = 0;
int t = i;
for (int k = 0; k < m; k++){
if (t & 1){
sum += an[n / 2 + k];
count++;
}
t >>= 1;
}
if (count == 0)
continue;
if (ll_abs(sum) < min_sum){
min_sum = ll_abs(sum);
min_count = count;
}
else if (ll_abs(sum) == min_sum){
min_count = min(min_count, count);
}
it = sum_map.lower_bound(-sum);
if (it != sum_map.end()){
long long int s = sum + it->first;
if (ll_abs(s) < min_sum){
min_sum = ll_abs(s);
min_count = it->second + count;
}
else if (ll_abs(s) == min_sum){
min_count = min(min_count, it->second + count);
}
}
if (it != sum_map.begin()){
--it;
long long int s = sum + it->first;
if (ll_abs(s) < min_sum){
min_sum = ll_abs(s);
min_count = it->second + count;
}
else if (ll_abs(s) == min_sum){
min_count = min(min_count, it->second + count);
}
}
}
printf("%lld %d\n", min_sum, min_count);
}
return 0;
}
原文：http://www.cnblogs.com/gtarcoder/p/4909448.html