bit全探索
(library/search/bit_search.hpp)

• View this file on GitHub
• Last update: 2026-01-07 21:05:45+09:00
• Include: #include "library/search/bit_search.hpp"

bit全探索

できること

• 集合Aの全パターンの部分集合を返す

  {1,2,3}
  ↓
  { {},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} }
  

計算量

$O(2^N)$ Nは20前後まで

使い方

vector<vector<int>> tmp = bit_search(A);

Verified with

• bit全探索のテスト (tests/search.bit_search.test.cpp)

Code

#pragma once
template <typename T> vector<vector<T>> bit_search(const vector<T> &A) {
    int N = A.size();
    vector<vector<T>> res;
    for (long long bit = 0; bit < (1ll << N); ++bit) {
        vector<T> tmp;
        for (int k = 0; k < N; ++k) {
            if (bit & (1ll << k)) {
                tmp.push_back(A[k]);
            }
        }
        res.push_back(tmp);
    }
    return res;
}

#line 2 "library/search/bit_search.hpp"
template <typename T> vector<vector<T>> bit_search(const vector<T> &A) {
    int N = A.size();
    vector<vector<T>> res;
    for (long long bit = 0; bit < (1ll << N); ++bit) {
        vector<T> tmp;
        for (int k = 0; k < N; ++k) {
            if (bit & (1ll << k)) {
                tmp.push_back(A[k]);
            }
        }
        res.push_back(tmp);
    }
    return res;
}

Back to top page