公式解説を前提とします．\(O(2^{N/4})\) 時間で解く方法を解説します．

次の問題を \(O(2^{K/2})\) 時間で解ければよいです．

長さ \(K\) の列 \(A\) と目標値 \(X\) が与えられた場合に，\(A\) の部分列で和が \(X\) に等しいものが存在するものがあれば求めよ．

\(A\) を「左半分」\(A_1\) と「右半分」\(A_2\) に分割し，半分全列挙により解くことを考えます．次の手順になります．

• (1) \(A_1\) のすべての部分列に対する和を列挙した列 \(S_1\) を求める．
• (2) \(A_2\) のすべての部分列に対する和を列挙した列 \(S_2\) を求める．
• (3) \(S_1\) の要素と \(S_2\) の要素の組であって和が \(X\) であるものを探す．

\(N_1 = |A_1|\), \(N_2 = |A_2|\) とします． (3) は \(S_1, S_2\) がソートされているという前提で，尺取り法により \(O(2^{N_1}+2^{N_2})\) 時間でできます．したがって，(1), (2) において \(S_1\), \(S_2\) をソートしたものを \(O(2^{N_1})\), \(O(2^{N_2})\) 時間で求められればよいです．整理すると，次に帰着されました．

長さ \(N\) の列 \(A\) が与えられる．\(A\) の部分集合の総和をすべて列挙してソートした列 \(S\) を \(O(2^N)\) 時間で出力せよ．

まず列がソートされているという条件を無視すれば，\(S\) は次の手順で計算できます．

• (1) \(S = (0)\) で初期化する．
• (2) 各 \(A\) の要素 \(a\) に対して次を行う：\(S = (x_1, \ldots, x_m)\) であるとき \(S\) を \((x_1, \ldots, x_m, x_1+a, \ldots,x_m+a)\) で置き換える．

このままでは出力はソートされませんが，手順 (2) を行うたびに \(S\) をソートすることにしましょう．このソートには一見 \(\Theta(m\log m)\) 時間かかりそうにも思えます．しかし手順 (2) のたびに \(S\) をソートしていれば，このソートは 「\(2\) つのソート済列のマージ」という形であるため，\(O(m)\) 時間で行うことができます．

一連の処理全体に対する \(m\) の和は \(\sum_{i=0}^{N-1}2^i = O(2^N)\) であるため，以上を適切に実装すれば目標が達成できます．

出典：https://x.com/noshi91/status/1271857111903825920