僕の友達は小さい (AOJ 2333)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2333

問題

略

解法

まず重さの低い順にソートをしておく。次にindex番目の友達以降を使って作れる重さを計算しておく。あとはindex番目の友達をリュックに入れない友達の中で最も軽い友達とした時に他の友だちの入れ方を数えれば良い。同じ重さの友達が複数いる場合はコンビネーションを使っててきとうに計算する。