No.15

半分全探索を使う.

商品を最初の $N/2$ 個 (グループ1) と残りの $N/2$ 個 (グループ2) でグループ分けしておく.

グループ2のすべての商品の組み合わせについて合計金額を計算し, 金額でソートしておく.

グループ1のすべての商品の組み合わせについて合計金額 $S_1$ を計算し, $S - S_1$ となる金額がグループ2に存在するかどうかを二分探索で探す.