\(a_i \geq K\) ならば部分集合 \(\{ a_i \}\) はよい集合であり, ここから \(a_i\) を取り除くとよい集合でなくなるので, 必要である.

そうでない場合は, \(a_i\) を除く要素の部分集合の総和が \([K-ai, K)\) になる組み合わせがひとつでもある場合, \(a_i\) とその組み合わせからなる部分集合はよい集合であり, そこから \(a_i\) を取り除くとよい集合でなくなるので, 必要である. \([K-ai, K)\) になる組み合わせを考えるので, \(K\) 以上の要素は考える必要はない.

\(a_i\) を除く要素の部分集合の総和が \(x\) になるかどうかは DP を使って求めることができるが, 計算量が \(O(NK)\) になる. これをすべての要素について行うと \(O(N^2K)\) となって部分点が取れる.

\(a_i\) が不必要だとすると, \(a_j \leq a_i\) となる \(a_j\) も不必要である. \(a_i\) を除く要素の部分集合で, \(a_j\) を含む部分集合と \(a_j\) を含まない部分集合に分ける. \(a_j\) を含まない部分集合は当然ながら \([K-a_j, K)\) にはなりえず, \(a_j\) を含む部分集合も \(a_j\) を \(a_i\) に置き換えると \([K-a_j, K)\) にはなりえない.

よって, \(a_i\) を昇順にソートして二分探索をすれば, 不必要な要素数を確定することができる.