最小選択部分和問題 Python3編（paizaランク A 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

N 個の数 a_1, a_2, ..., a_N と正の整数 K が与えられます。
a_1, a_2, ..., a_N からいくつかの要素を選んでその和を K とすることはできるかを判定してください。
ただし、1 つも選ばないときの和は 0 とします。
できるならその場合に選ぶ数の最小の個数を、できないなら -1 を出力してください。

入力される値

N K
a_1 a_2 ... a_N

・1 行目では数列の長さ N と正の整数 K が与えられます。
・2 行目で a_1, a_2, ..., a_N が空白区切りで与えられます。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: 答えを 1 行で出力してください。末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件: すべてのテストケースにおいて, 以下の条件をみたします

・入力はすべて整数
・1 ≦ N ≦ 1,000
・1 ≦ K ≦ 2,000
・1 ≦ a_i ≦ 100 (1 ≦ i ≦ N)

入力例1: 3 6
1 2 3

出力例1: 3

入力例2: 5 5
2 2 2 2 2

出力例2: -1

問題一覧へ戻る