F - #(subset sum = K) with Add and Erase
昨日の問題。
例えば2,3,5を数として持っているときに、5を2通り作れるが、3を取り出したときに2,3からできた5と単体の5を区別できるのか?と疑問だったが、
確かに3がなくなったとき、dp配列にはこれまでの2,3,5で作れる数の場合の数が入っているため、現在の5の場合の数から、3がなくなった場合の2の場合の数を引いてやることで、3を使っていたパターンだけを引くことができると考えると納得した。
また、この手順のときに加算の場合は降順、減算の場合は昇順にやらないと手順がダブってバグるので注意。