部分和問題 3 Go編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
1 ~ n の番号がついた n 個のおもりがあり、おもり i の重さは a_i です。
おもりを何個か選んで重さの和が x となるようにする方法を考えたとき、選ぶおもりの個数の最小値を出力してください。なお、同じおもりを2個以上選ぶことはできません。
なお、重さの和が x となるようにおもりを選ぶ方法が存在しない場合は-1と出力してください。
- 入力される値
-
n x
a_1
a_2
...
a_n・ 1行目に、おもりの個数 n と目標とする重さの和 x が半角スペース区切りで与えられます。
・ 続く n 行のうち i 行目では、おもり i の重さ a_i が与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
おもりを何個か選んで重さの和が x となるようにする方法のうち、選ぶおもりの個数の最小値を出力してください。
ただし、重さの和が x となるようにおもりを選ぶ方法が存在しない場合は-1と出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ n ≦ 100
・ 1 ≦ x ≦ 1,000
・ 1 ≦ a_i ≦ 100
- 入力例1
-
5 10
7
3
4
3
2
- 出力例1
-
2
