bit全探索をPythonとC++で実装してみた！

Pythonでbit全探索

{A, B, C}という集合の部分集合を全列挙するプログラム

N = 3
a = ['A', 'B', 'C']
for i in range(2**N):
    list = []
    for j in range(N):
        if(i & (1<<j)):
            list.append(a[j])
    print(list)

出力結果が以下の通り

[]
['A']
['B']
['A', 'B']
['C']
['A', 'C']
['B', 'C']
['A', 'B', 'C']

C++でbit全探索

{A, B, C}という集合の部分集合を全列挙するプログラム

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

    return 0;
}

出力結果は以下の通り

A
B
AB
C
AC
BC
ABC

最後にbit全探索を使ってAtcoder Beginer Congest 079の問題を解いてみた

atcoder.jp

int main() {
	string s;
	cin >> s;
	vector<int> a(4);
	rep(i,4) a[i] = s[i]-'0';

	for(int bit = 0; bit<(1<<3); bit++){
		string t = to_string(a[0]);
		int sum = a[0];
		for(int i = 0; i<3; i++){
			if(bit&(1<<i)){
				sum+=a[i+1];
				t+=("+" + to_string(a[i+1]));
			}else{
				sum-=a[i+1];
				t+=("-" + to_string(a[i+1]));
			}
		}

		if(sum == 7){
			cout << t << "=7" <<endl;
			return 0;
		}
	}


	return 0;
}