题意分析

给你一个含$n(n<=35)$个数的数组,让你在数组中选出一个非空子集，使其元素和的绝对值最小，输出子集元素的个数以及元素和的绝对值，若两个子集元素和相等，输出元素个数小的那个。

解题思路

如果直接暴力枚举，复杂度$O(2^n)$，$n$为$35$时会超时，故可以考虑折半枚举，利用二进制将和以及元素个数存在两个结构体数组中，先预判两个结构体是否满足题意，再将其中一个元素和取相反数后排序，因为总元素和越接近零越好，再二分查找即可，用$lower_bound$时考虑查找到的下标和他前一个下标，比较元素和以及元素个数，不断更新即可。

示例代码（C++）

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
struct Z
{
    long long int x;
    int y;
    bool operator < (const Z& b)const
    {
        if (x != b.x)
            return x < b.x;
        return y<b.y;

    }
}a[300005], b[300005];

long long  int c[40];

long long int abs1(long long int x)
{
    if (x<0)
        return -x;
    return x;
}

int main()
{
    int n;
    int i,j;
    while (cin >> n && n)
    {
        for (i = 0; i < 300005; i++)
        {
            a[i].x = a[i].y = b[i].x = b[i].y = 0;
        }
        long long sum = 1e17;
        int ans = 40;
        for (i = 0; i < n; i++)
        {
            cin >> c[i];
        }
        int n1 = n / 2;
        for (i = 0; i < (1 << n1); i++)//二进制枚举一半，共2的n1次方种
        {
            for (j = 0; j < n1; j++)
            {
                if (i >> j&1 && (i != 0 || j != 0))//这一半中的所有情况列出来
                {
                    a[i - 1].x+= c[j];
                    a[i - 1].y++;//记录这个数含有几个元素
                }
            }
        }
        int n2 = n - n1;
        for (i = 0; i < (1 << n2); i++)//同理初始化
        {
            for (j = 0; j < n2; j++)
            {
                if (i >> j & 1 && (i != 0 || j != 0))
                {
                    b[i - 1].x += c[j + n1];
                    b[i - 1].y++;
                }
            }
        }
        //对这两半单独检查更新最小和sum和最小元素数ans
        for (i = 0; i < (1 << n1) - 1; i++)//？
        {
            if (abs1(a[i].x) < sum)
            {
                sum = abs1(a[i].x);
                ans = a[i].y;
            }
            else if (abs1(a[i].x) == sum && a[i].y < ans)
            {
                ans=a[i].y;
                sum = abs1(a[i].x);
            }
        }

        for (i = 0; i<(1 << n1) - 1; i++)//前半部分变为相反数
            a[i].x = -a[i].x;
        for (i = 0; i<(1 << n2) - 1; i++) //另一半检查
        {
            if (abs1(b[i].x)<sum)
            {
                sum = abs1(b[i].x);
                ans = b[i].y;
            }
            else if (abs1(b[i].x) == sum && b[i].y<ans)
            {
                ans = b[i].y;
                sum = abs1(b[i].x);
            }
        }

        sort(a, a + (1 << n1) - 1);
        sort(b, b + (1 << n2) - 1);

        for (i = 0; i < (1 << n1)-1; i++)//两半合起来检查
        {
            int t = lower_bound(b, b + (1 << n2) - 1, a[i])- b;//t是序号
            if (t > 0)//查看该序号周围的数
            {
                if (abs1(b[t - 1].x - a[i].x) < sum)//和可以更小
                {
                    sum = abs1(b[t - 1].x - a[i].x);//更新最小绝对值和
                    ans = b[t - 1].y + a[i].y;//更新元素个数
                }
                else if (abs1(b[t - 1].x - a[i].x) == sum && b[t - 1].y + a[i].y < ans)//元素个数可以更小
                {
                    sum = abs1(b[t - 1].x - a[i].x);
                    ans = b[t - 1].y + a[i].y;
                }
            }
            if (t < (1 << n2) - 1)
            {
                if (abs1(b[t].x - a[i].x) < sum)
                {
                    sum = abs1(b[t].x - a[i].x);
                    ans = b[t].y + a[i].y;
                }
                else if (abs1(b[t].x - a[i].x) == sum && b[t].y + a[i].y<ans)
                {
                    sum = abs1(b[t].x - a[i].x);
                    ans = b[t].y + a[i].y;
                }
            }
        }
        cout << sum << " " << ans << endl;
    }
    return 0;
}