bit全探索について

「A～Z の文字から 1 文字以上を選んで作れるすべての文字列を列挙せよ。ただし、同じ文字は最大 1 回までしか使用できず、文字列中の文字の順番は問わない。（選んだ文字の組み合わせでできる "部分集合" のすべてを挙げること）」
という問題を想像してみてください。

例えば A～C なら「A」「B」「C」「AB」「AC」「BC」「ABC」と簡単に列挙できますよね。
でも A～F になるとどうでしょう？
「A」「B」「C」「D」「E」「F」と1文字パターンはまあ楽として、
「AB」「AC」「AD」「AE」「AF」「BC」「BD」... と2文字以上をすべて書き出すとなると、ちょっと苦労しませんか？
さらに A～Z まで広げると、もう手でやるなんて無理な話です。

こういうとき、競技プログラミングやアルゴリズムの世界では「bit全探索」というテクニックが大活躍します。
「bit全探索」とは何か？ 簡単にいうと、
「使う」or「使わない」をビット（0/1）で表し、全パターンを2進数のカウントアップで網羅する手法です。

たとえば A～C で考えると、文字 A,B,C にそれぞれビットを割り当てます。

• A：1ビット目
• B：2ビット目
• C：3ビット目

Aだけ使う場合は、Aに対応するビットが1で他が0なので「001」(2進表記)となり、10進数では1です。
Bだけ使う場合は「010」(2進)で10進だと2、Cだけなら「100」(2進)で10進で4。
ABなら「011」(2進)で10進では3、という具合に、2進数を用いることで「このビットパターンはどの文字を使うか」を表現できます。

こうすると 1 から 7(=2^3-1) までの数値を2進数で考えると、
A(001), B(010), C(100), AB(011), AC(101), BC(110), ABC(111) の全パターンが自然に得られるわけです。

この考え方は A～Z の26文字にも応用できます。
26文字全てを使うかどうかを示せば 2^26 - 1 通り！
とんでもない数ですが、コンピュータなら機械的な列挙は可能です。

C#で書くと、こんなコードになります。

for (int s = 1; s < (1 << 26); s++)
{
    string subset = "";
    for (int j = 0; j < 26; j++)
    {
        // sを右にjビットずらした結果の最下位ビットが1なら、その文字を使う
        if (((s >> j) & 1) == 1)
        {
            subset += (char)('A' + j);
        }
    }
    Console.WriteLine(subset);
}

これで s が1から 2^26-1 までカウントされるたびに、
ビットパターンに応じて対応する文字列が生成・出力されます。
Aだけ (…000001)、Bだけ (…000010)、…、ABC (…000111) という感じで、すべてが列挙されるわけです。

「なんか難しそう？」と思うかもしれませんが、
要は「すべての文字を入れる/入れないをビットで決めて、その二進法カウンタを回している」だけなのです。
これがbit全探索の強みです。

「うわ、樹形図がめんどくさそう」と思ったら、
bitで0/1の組み合わせを一気に扱う発想に飛び、実装はあとは for ループを回すだけ。
競プロでも多用するので、以前は手で書いてやろう！！とゴリ押ししていた私の自戒(次回)のためにもここで書かせていただきます。