Here is an algorithm that calculates the powerset of a set of elements given in a vector **input** of length **n**. A vector **bit** that will be used to select subsets is created and it’s elements are initialized with 1. Then for each subset size up to **n/2** (outer loop) a element of **bit** is switched from 1 to 0 (This way the vector is already sorted what is handy for the use of `std::next_permutation`

). Then the inner loop is entered which creates 2 subsets. The first consists of items in **input** where those items are selected, that have the same index as those which contain a 1 in **bit**. The other subset consists of items in **input** where the counterpart in **bit** contains 0. The subsets are added to the result. Then `std::next_permuation`

is called on **bit** creating the next permutation. The process is repeated until **bit** is in sorted order again, which signals that all permutations have been used. The last condition in the inner loop avoids adding subsets twice in case the **input** has even length.

template<typename T> std::vector<std::vector<T>> powerset(std::vector<T> const& input){ std::vector<std::vector<T>> rv{}; if(!input.empty()){ rv.push_back(input); } rv.push_back({}); std::size_t input_size = input.size(); std::vector bit(input.size(),1); bool even = (input_size % 2 == 0) ? true : false; std::size_t split_point = input_size/2; for(std::size_t i = 0; i < split_point; ++i){ bit[i]=0; do { std::vector tmp1; tmp1.reserve(i+1); std::vector tmp2; tmp2.reserve(input_size-(i+1)); for(std::size_t j = 0; j < input.size(); ++j){ if(bit[j]){ tmp1.push_back(input[j]); } else { tmp2.push_back(input[j]); } } rv.push_back(std::move(tmp1)); if(!((i == split_point-1) && even)){ rv.push_back(std::move(tmp2)); } } while (std::next_permutation(bit.begin(),bit.end())); } return rv; }