この問題は、動的計画法を使用することで解くことができます。
まず、駄菓子を順番に見ていき、\(i\) 番目まで選んだ時に、\(j\) 円で買えるかを判定します。
例えば入力例１だと、１個目まで選ぶと使用できる金額は０円、１０円になります。２個目まで選ぶと、０円から派生する金額は０円、２０円、１０円から派生する金額は１０円、３０円となります。
ここで、\(M\) 円を超える金額は記録しないようにしましょう。
こうすることで、\(2^N\) 通りを試さずに、\(O(NM)\) で求められます。
実装例