問題リンク
問題概要
省略
解法
\(dp[i][j] =\) {\(A_1,...,A_i\)の各部分集合に対する、和がjとなる部分集合の数}
と置いてDPする。
遷移は
\(dp[i+1][j] = 2dp[i][j] + dp[i][j-A_{i+1}]\)
となる。
右辺の第1項は\(A_i\)を含む集合(ただし和には使わない)と含まない集合両方を合わせた遷移、
第2項は\(A_i\)を含む集合で和にも使う場合を考えた遷移に対応する。
提出
https://atcoder.jp/contests/abc169/submissions/13824819
感想
All Segmentsの方が難しい気がする。
