ビット全探索 入門 2 PHP編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
次は、ビット全探索を使う問題を解いてみましょう。
要素数 N の整数の集合 S があたえられます。
集合 S の部分集合のうち、以下の条件を満たす部分集合をすべて出力してください。
・ 条件：部分集合の要素の総和が K 以上である
出力は、以下の出力形式に従ってください。
出力するビット列を B、そのビット列に対応する部分集合の要素を t_1, t_2, t_3 ... としたとき、以下の形式で出力してください。 B {t_1 t_2 t_3 ...}
ただし、集合 S の各要素を値の小さい順にビット列の下位から順に対応させることとします。
出力例も参照してください。
なお、条件を満たす部分集合が必ず 1 つ以上存在することが保証されます。
- 入力される値
-
N K
S_1 S_2 ... S_N
・ 1 行目には整数 N, K が与えられます。
・ 2 行目には、集合の要素 S_i が空白区切りで与えられます。
・ 入力は合計で 2 行からなり、入力値最終行の末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
集合 S の部分集合のうち、部分集合の要素の総和が K 以上であるものを重複なくすべて出力してください。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ N ≦ 8
・ 0 ≦ K ≦ S_1 + S_2 + ... + S_N
・ 0 ≦ S_1 < S_2 < ... < S_N ≦ 10^5
- 入力例1
-
3 2
0 1 3
- 出力例1
-
100 {3}
101 {0 3}
110 {1 3}
111 {0 1 3}
- 入力例2
-
5 1564
76 398 567 631 778
- 出力例2
-
11100 {567 631 778}
11101 {76 567 631 778}
11010 {398 631 778}
01111 {76 398 567 631}
10110 {398 567 778}
10111 {76 398 567 778}
11111 {76 398 567 631 778}
11110 {398 567 631 778}
11011 {76 398 631 778}
01110 {398 567 631}
