Power Set

8.4 Power Set: Write a method to return all subsets of a set.

• The power set intuitively represents all the possible subcombinations you can have in given set. In other words, the power set represents all possible combinations for k = 0...n, where n is the length of the set.

• The power set gross at pow(2, k), where k is the length of the set.

ex.

case 1: {}                            = P(0) (empty set);       2^0 = 1
case 2: {}, {a}                    = P('a');                2^1 = 2
case n: {}, {a}, {b}, {ab}         = P('ab');               2^2 = 4

' ' a 
' ' a b ab 
' ' a b ab c ac bc abc 
' ' a b ab c ac bc abc d ad bd abd cd acd bcd abcd

• Pascals triangle provides us the amount of combinations per level, for any 'choose'. The growth is exponential.

• Every additional case feeds on the previous cases by appending a additional unique element to the end of the string.

vector<string> power_set(string str) {
    int size = pow(2, str.length());
    vector<string> build;//(size);

    build.push_back(" ");

    if (str.length() >= 1) {
        string temp(1, str[0]);
        build.push_back(temp);
    }

    for (int i = 1; i < str.length(); i++) {
        int cur_size = build.size();
        for (int j = 0; j < cur_size; j++) {
            string temp = build[j];
            temp.insert(temp.end(), str[i]);
            //print(build);
            build.push_back(temp);
        }
    }

    return build;
}

int main()
{
    vector<string> p_set = power_set("a");
    print(p_set);

    p_set = power_set("ab");
    print(p_set);

    p_set = power_set("abc");
    print(p_set);

    p_set = power_set("abcd");
    print(p_set);

    p_set = power_set("abcde");
    print(p_set);
}