Enumerate Subsets
(misc/enumerate_subsets.hpp)

• View this file on GitHub
• Last update: 2022-06-27 13:45:26+09:00
• Include: #include "misc/enumerate_subsets.hpp"

Code

#pragma once
#include <vector>

/**
 * @brief Enumerate Subsets
 */
std::vector<int> enumerate_subsets(int n, int k) {
    if (k < 0 || n < k) return {};
    if (k == 0) return {0};
    std::vector<int> ret;
    int comb = (1 << k) - 1;
    while (comb < (1 << n)) {
        ret.push_back(comb);
        int x = comb & -comb;
        int y = comb + x;
        comb = ((comb & ~y) / x >> 1) | y;
    }
    return ret;
}

#line 2 "misc/enumerate_subsets.hpp"
#include <vector>

/**
 * @brief Enumerate Subsets
 */
std::vector<int> enumerate_subsets(int n, int k) {
    if (k < 0 || n < k) return {};
    if (k == 0) return {0};
    std::vector<int> ret;
    int comb = (1 << k) - 1;
    while (comb < (1 << n)) {
        ret.push_back(comb);
        int x = comb & -comb;
        int y = comb + x;
        comb = ((comb & ~y) / x >> 1) | y;
    }
    return ret;
}

Back to top page