解説

・部分点解法

この問題において、制約の $N$ が $N \leq 20$ と小さいので残すべき積み木の組み合わせ $2^N \leq 1048576 \fallingdotseq 10^6$ 通りを全て列挙しても余裕で間に合います。(bit全探索)

後はその中から要素の和が $K$ になるような組み合わせを一つ見つけて出力すれば良いです。$K = 0$ のときに一つも積み木を残さない組み合わせを選ばないように注意してください。

時間計算量は組み合わせの列挙に $O(2^N)$ 、列挙した組み合わせそれぞれに対しその要素の和が $K$ に等しいか判定するのに $O(N)$ かかるので、全体として $O(N \times 2^N)$ となります。

・満点解法

こちらは制約の $N$ が $N = 40$ となり、残すべき積み木の組み合わせ $2^N \leq 1099511627776 \fallingdotseq 10^{12}$ 通りを愚直に全列挙すると確実に間に合いません。

では、どのようにすればよいのでしょうか。ここでは、半分全探索というテクニックを使います。

まず、$N$ 個の積み木を $\lfloor N//2 \rfloor$ 個と $\lceil N//2 \rceil$ 個の $2$ つのグループ(便宜上 $A,B$ とする)に分割します。そして、各グループについて、残すべき積み木の組み合わせを全列挙し、それぞれの組み合わせについてその要素の和を計算してその値を持っておきます。

そして、$A$ の各組み合わせ $a_i$ について、その和を $S_{a_i}$ としたときに、 $B$ の組み合わせ $b_j$ でその和が $K-S_{a_i}$ となるようなものを二分探索で探し、見つかれば $a_i,b_j$ の要素を全て出力すれば良いです。

計算量を考えます。各グループについて、残すべき積み木の組み合わせを全列挙、組み合わせについてその要素の和を計算するのに $O(N \times 2^{\frac{N}{2}})$ となり、そのあとの操作は $A,B$ の組み合わせの個数をそれぞれ $|A|,|B|$ とすると $O(|A|log(|B|))$ となり、ここで $|A| \fallingdotseq |B| \fallingdotseq 2^{\frac{N}{2}}$ であるため、全体の時間計算量は $O(N \times 2^{\frac{N}{2}}+2^{\frac{N}{2}}log(2^{\frac{N}{2}})) = O(N \times 2^{\frac{N}{2}})$ となります。

部分点解法と同様に$K = 0$ のときに一つも積み木を残さない組み合わせを選ばないように注意してください。