bit全探索って何？

ビット全探索とは

二進数とビットを用いて、ある集合の部分集合を全列挙するアルゴリズムの事を言う。

例えばABCという集合ならば、
{},{A},{B},{C},{AB},{AC},{BC},{ABC}という８個の部分集合に分けられる！
これをC++でプログラムを書くと...

#include <bits/stdc++.h>
using namespace std;

int main(){
    string t="ABC";
    for (int bit=0; bit<(1<<3); bit++){
        string s="";
        for (int i=0; i<3; i++){
            if (bit&(1<<i)) s+=t[i];
        }
        cout << "{" << s << "}" << endl;
    }
}

#出力結果
{}
{A}
{B}
{AB}
{C}
{AC}
{BC}
{ABC}

問題と提出コード

以下の問題はbit全探索に慣れるためにそれを用いて記述しました。そのためこれらの問題には、より簡単な解法が存在します。

第一問　C - Train Ticket

問題概要

４桁の番号が与えられる。番号と番号の間全てに+か-を挿入してその演算結果が7になるものを出力せよ。

解法

'+'か'-'の2通りを全探索すれば良いことが問題文から見て取れます。高々2^3回のループなので全探索で問題ありません。

#include <bits/stdc++.h>
using namespace std;

int main(){
        string s,t;
        cin >> s;
        t=s[0];
        int sum=0;
        //2^3回ループ
        for (int bit=0; bit<(1<<3); bit++){
                int a;
                //文字列をintに変換
                sum=s[0]-'0';
                t=s[0];
                for (int i=0; i<3; i++){
                        a=s[i+1]-'0';
                        //bitが立ってたら+
                        if(bit & (1<<i)) {
                                sum+=a;
                                t=t+'+'+s[i+1];
                        }else{  //bitが立っていなかったら-
                                sum-=a;
                                t=t+'-'+s[i+1];
                        }
                }
                //和が7なら文字列を出力
                if(sum==7) {
                        cout << t << "=7" << endl;
                        break;
                }
        }
        return 0;
}

まとめ

①全ての部分集合をbitで０と１のみで表す！

②集合を一つずつ分ける

ex)ABC→'A','B','C'
そのあと、if文で一文字ずつあるか無いかを確かめれば、if,else含めて、全てを参照することができる！