#include <bits/stdc++.h>

//*************************************************************************
// HackerRank Prepare > Mathematics > Combinatorics: Building a List
//*************************************************************************

// 12    1 12 2
// yz -> y yz z

// 123    1 12 123 13 2 23 3
// xyz -> x xy xyz xz y yz z

// 1234    1 12 123 124 1234 13 134 14 2 23 234 24 3 34 4
// wxyz -> w wx wxy wxz wxyz wy wyz wz x xy xyz xz y yz z
//
// 1 2 3 4
// 12 13 14
// 23 24
// 34
// 123 134
// 234
// 1234

// Bitmask
// wxyz
//
// 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101
// z    y    yz   x    xz   xy   xyz  w    wz   wy   wyz  wx   wxz
//
// 1110 1111
// wxy  wxyz

using namespace std;

void brute_force();

int main()
{
    string s = "wxyz";
    
    uint64_t n = s.size();
    
    vector<string> si;

    cout << "size: " << n << " size^2: " << pow(2, n) << endl;
    cout << "str: " << s << endl;    
    
    for (uint64_t i = 1; i < pow(2, n); i++)
    {
        string rt = "";
        for (uint64_t j=0; j<n; j++)
        {
            if (i & (1<<j) )
            {
                bitset<4> bs_i(i);                
                bitset<4> bs_j(1<<j);
                bitset<4> bs_i_and_j(i & (1<<j));                
                cout << "i: " << i << " " << bs_i << " "
                     << "j: " << j << " " << bs_j << " "
                     << "i&(1<<j) " << (i & (1<<j)) << " "
                     << bs_i_and_j
                     << endl;
                rt += s[j];
            }
        }
        cout << "chars: " << rt << endl;        
        cout << " -------- " << endl;        
        si.push_back(rt);
    }
    
    sort(si.begin(), si.end());

    for (auto i: si)
        cout << i << endl;

    cout << " ----- brute_force ------" << endl;
    
    brute_force();

    return 0;
}

void brute_force()
{
    string s = "wxyz";
    
    for (size_t i=0; i < s.size(); i++)
    {
        cout << s[i] << endl;
        for (size_t j = i + 1; j < s.size(); j++)
        {
            cout << s[i] << s[j] << endl;
            for (size_t k = j + 1; k < s.size(); k++)
            {
                cout << s[i] << s[j] << s[k] << endl;
                for (size_t l = k+1; l < s.size(); l++)
                {
                    cout << s[i] << s[j] << s[k] << s[l] << endl;
                }
            }
        }
    }
}