B18 - Subset Sum with Restoration Editorial /

Time Limit: 1 sec / Memory Limit: 1024 MB

配点 : 1000

問題文

N 枚のカードが一列に並べられており、左から i 番目のカード(以下、カード i とする)には整数 A_i が書かれています。カードの中からいくつかを選んで、書かれた整数の合計が S となるようにする方法が存在するか判定し、存在する場合はその方法を 1 つ求めてください。

制約

  • 1 \leq N \leq 60
  • 1 \leq S \leq 10\,000
  • 1 \leq A_i \leq 10\,000
  • 入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N S
A_1 A_2 \cdots A_N

出力

カードの中からいくつかを選んで、書かれた整数の合計が S となるようにする方法が存在する場合、選ぶカードの番号を P_1, P_2, …, P_K として以下の形式で出力してください。

K
P_1 P_2 \cdots P_K

そのような方法が存在しない場合、-1 を出力してください。


入力例 1

3 7
2 2 3

出力例 1

3
1 2 3

カード 1・カード 2・カード 3 を選んだ場合、書かれた整数の合計は 2+2+3=7 となります。


入力例 2

3 10
1 2 4

出力例 2

-1

入力例 3

10 100
14 23 18 7 11 23 23 5 8 2

出力例 3

6
2 3 6 7 8 9