半分全列挙 (コインの組み合わせ II)

AOJ 
// i枚選んだときの作れる価値リスト
VV f(VI& A){
  ll N = SZ(A);
  VV G(N+1); // 0枚からN枚
  // 全列挙
  rep(f,1<<N){
    ll sum=0;
    ll cnt=0;
    rep(i,N){
      if(f>>i&1){
        sum += A[i];
        cnt++;
      }
    }
    G[cnt].push_back(sum);
  }
  // ソートしとくか
  rep(i,N+1){
    SORT(G[i]);
  }
  return G;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,K,L,R;
    cin>>N>>K>>L>>R;

    ll N0 = N/2;
    ll N1 = N-N0;

    VI A(N);
    rep(i,N)cin>>A[i];

    VV G,F;
    // 前半部
    {
      VI B;
      rep(i,N0)B.push_back(A[i]);
      G = f(B);
    }
    // 後半部
    {
      VI B;
      FOR(i,N0,N)B.push_back(A[i]);
      F = f(B);
    }

    ll cnt=0;
    rep(i,N0+1){
      // 前半からi枚選んだ場合
      for(ll value : G[i]){
        // 後半部から対応する範囲を二分探索
        ll j = K-i;
        if(j<0) continue;
        if(j==0){
          if(L<=value and value<=R)cnt++;
        }else{
          // 後半からはj枚選ぶぞー
          if(j>N1)continue;
          // 前半でvalue分選んだので
          ll left = L-value;
          ll right = R-value;
          auto it = lower_bound(ALL(F[j]), left);
          auto it2 = upper_bound(ALL(F[j]), right);
          ll num = it2-it;
          cnt += num;
        }
      }
    }
    p(cnt);

    return 0;
}

類題