"個の組み合わせがあります。(i=1,2,.....,L)が与えられている。この中から任意の個数の要素を選んで、その総和が目標値Tになるようにしたい。そのような選び方を全部示せ。結局の所総当たりで調べるしかなさそう(NP問題)ですが、無駄な探索を省くと少しは速くなります。そのためには・値をsortしておくことによって、見込みのない探索を早く打ち切ることができます。(i=1,2,.....,L)が与えられている。この中から任意の個数の要素を選んで、その総和が目標値Tになるようにしたい。そのような選び方を全部示せ。結局の所総当たりで調べるしかなさそう(NP問題)ですが、無駄な探索を省くと少しは速くなります。そのためには・値をsortしておくことによって、見込みのない探索を早く打ち切ることができます。・値が0である要素は、加えても加えなくても合計値は変わらない。・同じ値が複数個入っている場合も、その取捨選択の組み合わせを変えたところで合計値は変わらない。幾つ選択できるかは、個数による。これらを考慮しないと無駄な探索をやってしまうことになります。・正の値と負の値は区別して扱う必要がある。これが問題を難しくしている。(もしlistに正の値しか現れないというのだと、だいぶすっきりしたものになる。)というのも重要な点です。これらを盛り込んでみると、以下の通り。listを値が小さい順にsortする。値が0の要素は除外する。その結果をV[j](j=1,...,N)とする。L-Nはlistに含まれていた0の個数である。)すると、以下の性質が成り立つ。(Σ{x∈X}V[x]とは、Xに含まれる全ての要素xについてV[x]の総和を取ることを示す。この準備をした上で、Solve(T)を走らせればOK。(空集合φは一つの解である。この解に随伴する全ての答を生成する。