第k小子集

有n个数，共有2^n个子集，一个子集的值看做其所有数的和。
求这2^n个子集中第K小的子集。
n<=35。

meet in the middle + 二分判定

注意在双指针逼近时，相等的数带来的影响

#include<cstdio>

#include<algorithm>

#define N 262500

using namespace std;

int n,k,a[],half,note;

int tmp1[N],sum1,tmp2[N],sum2;

int l,r,mid,ans;

void dfs(int now,int tot,int *tmp,int &sum)

{

    if(now>note) { tmp[++sum]=tot; return; }

    dfs(now+,tot,tmp,sum);

    dfs(now+,tot+a[now],tmp,sum);

}

bool check()

{

    int j=sum2,cnt1,cnt2,tot=,last=;

    for(int i=;i<=sum1;i++)

    {

        while(j && tmp1[i]+tmp2[j]>mid) j--;

        if(!j) break;

        cnt1=cnt2=;

        while(i<sum1 && tmp1[i+]==tmp1[i]) i++,cnt1++;

        while(j> && tmp2[j-]==tmp2[j]) j--,cnt2++;

        tot+=last;

        if(tot>=k) return false;

        last=cnt1*cnt2;

    }

    return true;

}

int main()

{

    scanf("%d%d",&n,&k); half=n>>;

    for(int i=;i<=n;i++) scanf("%d",&a[i]),r+=a[i];

    note=half;

    dfs(,,tmp1,sum1);

    note=n;

    dfs(half+,,tmp2,sum2);

    sort(tmp1+,tmp1+sum1+);

    sort(tmp2+,tmp2+sum2+);

    while(l<=r)

    {

        mid=l+r>>;

        if(check()) ans=mid,l=mid+;

        else r=mid-;

    }

    printf("%d",ans);

}