Exhaustive Search (bit 全探索)
(lib/others/exhaustive_search.hpp)

• View this file on GitHub
• Last update: 2024-05-04 18:06:16+09:00
• Include: #include "lib/others/exhaustive_search.hpp"

Exhaustive Search (bit 全探索)

概要

a の部分集合の和の組み合わせをすべて列挙します。

bit 全探索のサンプルコードです。

計算量

a の要素数を $N$ とすると、$\mathrm{O}(N 2^N)$

Verified with

• test/aoj/alds1/alds1_5_a.test.cpp

Code

#pragma once

/**
 * @brief Exhaustive Search (bit 全探索)
 * @docs docs/others/exhaustive_search.md
 */

template<typename T>
vector<long long> sum_subsets(T a){
    vector<long long> res;
    int n = a.size();
    for(int bit = 0; bit < (1 << n); bit++){
        long long sum = 0;
        for(int i = 0; i < n; i++){
            int mask = 1 << i;
            if(bit & mask){
                sum += a[i];
            }
        }
        res.emplace_back(sum);
    }
    return res;
}

#line 2 "lib/others/exhaustive_search.hpp"

/**
 * @brief Exhaustive Search (bit 全探索)
 * @docs docs/others/exhaustive_search.md
 */

template<typename T>
vector<long long> sum_subsets(T a){
    vector<long long> res;
    int n = a.size();
    for(int bit = 0; bit < (1 << n); bit++){
        long long sum = 0;
        for(int i = 0; i < n; i++){
            int mask = 1 << i;
            if(bit & mask){
                sum += a[i];
            }
        }
        res.emplace_back(sum);
    }
    return res;
}

Back to top page