# Power Set in C++

In this article, we will discuss power set in C++ with several examples:

## What is a powerset?

All of the subsets of a set S make up its powerset. For instance, the powerset of the set {a, b, c} is {{}, {a}, {b}, {c}, {ab}, {ac}, {bc}, {abc}}.

### Significance of powersets in various applications:

Powersets can be used for several purposes, such as:

• Powersets can be used to find solutions to various combinatorial issues, such as counting the possible arrangements of a given set of objects or calculating the highest possible weight of a knapsack.
• Set operations: A variety of set operations, including union, intersection, and difference, can be carried out using powersets.
• Graph Algorithms: A variety of network algorithms, such as determining the shortest path between any two nodes or the largest clique in a graph, can be implemented using powersets.
• Powersets can represent features in machine learning techniques like decision trees and support vector machines.

### Powerset implementation:

In C++, recursive functions can be used as one method of powerset implementation. The following function produces the powerset of a specific set S:

```#include <vector>

#include <iostream>

using namespace std;

vector<vector<int>> powerset(vector<int> S) {

vector<vector<int>> subsets;

for (int num : S) {

int numSubsets = subsets.size();

for (int i = 0; i < numSubsets; ++i) {

vector<int> newSubset = subsets[i];

newSubset.push_back(num);

subsets.push_back(newSubset);

}

}

return subsets;

}

int main() {

vector<int> input = {1, 2, 3, 4, 5};

vector<vector<int>> result = powerset(input);

for (vector<int> subset : result) {

for (int num : subset) {

cout << num << " ";

}

cout << endl;

}

return 0;

}```

Output:

The code that follows demonstrates how to create a bitmask-based powerset from a given set:

```#include <bitset>

#include <iostream>

#include <vector>

using namespace std;

vector<vector<int>> powerset(vector<int> inputSet) {

int n = inputSet.size();

bitset<32> bitmask(0); // Use an appropriate size for the bitset

vector<vector<int>> subsets;

for (int i = 0; i < (1 << n); i++) {

vector<int> subset;

for (int j = 0; j < n; j++) {

subset.push_back(inputSet[j]);

}

}

subsets.push_back(subset);

int j = 0;

while (j < n && bitmask[j]) {

j++;

}

if (j < n) {

}

}

return subsets;

}

int main() {

vector<int> inputSet = {1, 2, 3, 4};

vector<vector<int>> result = powerset(inputSet);

for (vector<int> subset : result) {

for (int num : subset) {

cout << num << " ";

}

cout << endl;

}

return 0;

}```

Output:

Powersets are an effective tool that may be utilized in C++ and other programming languages to address various issues.

Here's how this pseudocode functions:

• The powerset of S is the empty set if the set S is empty.
• If not, we remove the final element from S and put it in the variable last.
• After that, the powerset() function is recursively called on S's remaining elements. It produces the powerset of S's remaining components.
• Next, the remaining S elements' powerset is iterated over. We include the final member of S in each subgroup.
• The powerset of S is returned, composed of the subsets with the final element of S added and the powerset of the other parts of S.

## Recursive Approach:

The recursive method for constructing a set's powerset is recursive because it calls itself to build the powerset of the set's remaining components. When the set is empty, the powerset of the set is just the empty set. This procedure continues until the set is empty.

The following pseudocode represents the recursive algorithm for creating a set's powerset:

```function powerset(S):

if S is empty:

return {empty set}

last = S.pop()

subsets = powerset(S)

for subset in subsets:

subset.append(last)

return subsets```

Example:

```#include <iostream>

#include <vector>

using namespace std;

vector<vector<int>> powerset(vector<int> S) {

if (S.empty()) {

return {{}};

}

int last = S.back();

S.pop_back();

vector<vector<int>> subsets = powerset(S);

int numSubsets = subsets.size();

for (int i = 0; i < numSubsets; ++i) {

vector<int> newSubset = subsets[i];

newSubset.push_back(last);

subsets.push_back(newSubset);

}

return subsets;

}

int main() {

vector<int> input = {1, 2, 3};

vector<vector<int>> result = powerset(input);

for (vector<int> subset : result) {

cout << "{";

for (int i = 0; i < subset.size(); ++i) {

cout << subset[i];

if (i < subset.size() - 1) {

cout << ", ";

}

}

cout << "}" << endl;

}

return 0;

}```

Output:

Time and Space Complexity:

• The recursive method of producing the powerset of a set takes O(2n) time, where n is the set's size. The time complexity is because the recursive function calls itself 2^n times for each potential subset of the set.
• The recursive method of constructing a set's powerset has an O(n) space complexity, where n is the set's size. The time complexity is because a stack of frames must be stored each time a recursive function is called.
• The time complexity of the recursive method and the iterative method for creating a powerset of a set is O(2n). However, the iterative method has a better space complexity, O(1), than the recursion method. The time complexity is because the iteration method does not require the storage of a stack of frames.