string_subsets.cc

#include <iostream>
#include <string>
#include <math.h>
#include <boost/dynamic_bitset.hpp>

void print_subsets(const std::string &str) {
    std::cout << "[empty string]\n";

    const int n = str.size();

    if (n < 1) return;

    const unsigned subsets_num = (unsigned) pow(2, n);
    boost::dynamic_bitset<> binary_num; // O(n) space
    int i, j;

    // O(2^n) time
    for (i = 1; i < subsets_num; i++) { // skip empty string, which we already printed
        binary_num = boost::dynamic_bitset<>(n, i); // re-used

        // O(n) time
        for (j = 0; j < n; j++)
            if (binary_num[j])
                std::cout << str[j];

        std::cout << "\n";
    }
}

int main() {
    print_subsets("abc");
    return 0;
}