https://atcoder.jp/contests/abc271/submissions/61497852
$s$ を作成できるかどうかだけを考える。
$$ \mathrm{dp}[i][j] := \text{i枚目までのカードでjを作れるか} $$
このdpを使って $\mathrm{dp}[n][s] = \text{true}$ になれば $s$ を作れることになる。
ここで $\mathrm{dp}[i][j] = \text{true}$ のときに、どの数字から遷移したかをメモしておく配列を作る。
$$ \mathrm{prev}[i][j] := \text {if} \,\, \mathrm{dp}[i][j] = \text{true } \\ \text{dp[i-1]にある遷移元の値} $$
このように $\mathrm{prev}$ を定義してあげると簡単に復元できる。
この考え方はBFS等でも使用できる。
提出