# 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);
}``````

Last updated