折半搜索（meet in the middle）和two point；

题目：有n个数，共有2^n个子集，一个子集的值看做其所有数的和。

求这2^n个子集中第K大的子集。

n<=35.

观察数据范围，如果直接搜索会爆栈的，所以就有了折半搜索。

将两部分的结果两两任意组合就构成了所有的集合。

用二分（判定用two point）来判断

代码（二分有点问题，暂且贴上，还望指正）：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int n,a[1009],k;int b[(1<<20)],c[(1<<20)],cnt1=1,cnt2=1;int L,R;void dfs1(int x,int sum){    if(x>n/2) return;    b[++cnt1]=sum+a[x];    dfs1(x+1,sum+a[x]);    dfs1(x+1,sum);}void dfs2(int x,int sum){    if(x>n) return;    c[++cnt2]=sum+a[x];    dfs2(x+1,sum+a[x]);    dfs2(x+1,sum);}int check(int x){    int t1=1,t2=cnt2,sum=0;    while(t1<=cnt1&&t2>=1)    {        while(b[t1]+c[t2]>=x&&t2>=1) t2--;        sum+=t2;        t1++;    }    return sum;//比它小的有sum个 }int main(){    scanf("%d%d",&n,&k);    for(int i=1;i<=n;i++) scanf("%d",&a[i]),R+=a[i];    dfs1(1,0);    dfs2(n/2+1,0);//折半搜索    sort(b+1,b+cnt1+1);    sort(c+1,c+cnt2+1);    k=(1<
         
          >1;        if(check(mid)>=k) R=mid-1;//子集中没有重复要把 = 去掉！！！！！！！！！！         else L=mid+1;    }     printf("%d",R);    return 0;}