まず \(M=X\) の場合を考えます。

\(X\) 以上の整数は用いる必要がないため \(X\) が小さい場合は全探索できます（\(X=3,5,6,9,10\) の場合は不可能ということも分かります）。

また、 \(X \ge 16\) のときは次の手続きで \(S\) を構成できます。

• 総和が \(X\) 以上になる直前まで \(S = \lbrace 1, 2, 4, 8, \dots \rbrace\) と \(2\) 冪を順に \(S\) に加える
• \(x:=X-1-\mathrm{sum}(S) > 0\) ならば \(x\) を \(S\) に加える
  • ただし \(x\) も \(2\) 冪の場合は要素の重複が起こるので、 \(S\) の最後の要素を \(-1\) か \(-2\) するなどの調整を事前にして避ける

\(M>X\) の場合は、上記のようにして作った \(S\) に適切に要素を追加すればよいです。例えば、 \(2^i (X+1)\ (i \ge 0)\) を追加することで、 \(k = (X+1)n + X\ (n \ge 1)\) と書ける \(k\) を除いて条件を満たせます。さらに \(2X + 1\) も追加することで条件を全て満たせます。

この解法では \(S\) の要素数は \(19\) 以下にできます。