ビット全探索 入門 1 Swift編（paizaランク C 相当）

説明

この章では、ビット全探索について学んでいきます。
ビット全探索とは、ビット列を用いて集合の部分集合をすべて列挙するアルゴリズムです。

ある集合の部分集合をビット列で表現する方法を考えます。
集合の各要素に対応するビットが 1 か 0 かでその要素を含むかどうかを表現することにします。
要素数 N の集合の部分集合は N 桁のビット列によって表されます。
例えば、集合 {1, 2, 4, 7} の部分集合をビット列で表現することを考えます。
ここでは、集合の各要素を値の小さい順にビット列の下位から順に対応させることにします。
すると、ビット列 0101 は部分集合 {1, 4} を、ビット列 1001 は部分集合 {1, 7} を表します。
このように、各要素が含まれるか否かを表すビット列を使って表現することで、部分集合を列挙することができます。
ここで、整数を 2 進数表記したものをビット列として考えると、N 桁のビット列は整数 0 ~ 2^N - 1 を用いて表現できます。
例えば、整数 9 に対応する 4 桁のビット列は 1010 であり、このビット列が表す部分集合は {2, 7} です。

問題

要素数 N の整数の集合 S があたえられます。
集合 S の部分集合を表すビット列とそのビット列に対応する部分集合の要素をすべて出力してください。

出力は、以下の出力形式に従ってください。
出力するビット列を B、そのビット列に対応する部分集合の要素を t_1, t_2, t_3 ... としたとき、以下の形式で出力してください。
B {t_1 t_2 t_3 ...}
ただし、集合 S の各要素を値の小さい順にビット列の下位から順に対応させることとします。
出力例も参照してください。