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
Was this helpful?