The power set represents a compilation of all subsets, inclusive of the empty set and the initial set itself. Developing the power set of a set can be accomplished through a recursive technique or an iterative method that incorporates bitwise operations. A set comprises distinct elements, while an empty set denotes a set devoid of any elements; the power set encompasses all feasible subsets of a specified set.
Understanding the Problem:
We are presented with an array containing 'N' elements, denoted as [a, b, c]. Our task is to generate a power set for this array, ensuring that each subset within the power set is organized in ascending sequence. The resulting array should consist of subsets where the elements are sorted in ascending order. The sequence of subsets within the output array is not significant.
Example with [a, b, c]:
Suppose we begin with the collection [a, b, c]. Various subgroups of this collection are listed below:
[a, b]
[a, c]
[b, c]
[a, b, c]
Now, the power set refers to the complete gathering of all these subsets.
- An empty set
- Set containing 'a'
- Set containing 'b'
- Set containing 'a' and 'b'
- Set containing 'c'
- Set containing 'a' and 'c'
- Set containing 'b' and 'c'
- Set containing 'a', 'b', and 'c'
Method 1: Brute Force Approach
We will begin with null sets and iterate through them over 'N' iterations, where 'N' represents the original array size [a, b, c]. Each iteration presents two options: either adding or omitting the element currently under consideration.
Let's use the example where 'N' is set to 3, and the contents of the input array are [a, b, c] to demonstrate this method.
- Step 0: Begin with an empty set, [] .
- Step 1: Make duplicates of the previous subsets. In one copy, add 'a' to each subset; in another copy, leave the subsets alone. As a result, [, [a]].
- Step 2: Make two additional copies of the previous step's subsets. In one of the copies, add 'b' to each subset; in the other, leave the subsets alone. The subsets are now doubled: [, [a], [b], [a, b]].
- Step 3: Make two duplicates of the subsets from the previous step. In one copy, add 'c' to each subset; in the other, leave the subsets alone. It generates the following power set: [, [a], [b], [a, b], [c], [a, c], [b, c], [a, b, c], [a, b, c]].
If we aim to create the power set, this approach meticulously evaluates all potential combinations of adding and omitting each item (a, b, and c) in the list [a, b, c]. Every iteration exponentially increases the overall number of subsets within the power set, resulting in the complete collection of all feasible subsets.
Example:
Let's consider an example to demonstrate the power set algorithm in C++.
#include <iostream>
#include <vector>
using namespace std;
vector<vector<char>> powerSet(vector<char> &array)
{
int l = array.size();
// array for storing the result
vector<vector<char>> answer = {{}};
// iterating over the array
for (int i = 0; i < l; i++)
{
char element = array[i];
int len = answer.size();
// traverse through the array answer
for (int j = 0; j < len; j++)
{
vector<char> tem = answer[j];
// element included
tem.push_back(element);
answer.push_back(tem);
}
}
// Return the array ?answer?.
return answer;
}
int main()
{
// user input
int number;
cin >> number;
vector<char> array(number);
for(int i = 0; i < number; i++)
cin >> array[i];
// function calling
vector<vector<char>> answer = powerSet(array);
// displaying the result
for(int i = 0; i < answer.size(); i++){
for(int j = 0; j < answer[i].size(); j++)
cout << answer[i][j] << " ";
cout << endl;
}
return 0;
}
Input:
3
a
b
c
Output:
a
b
a b
c
a c
b c
a b c
Complexity:
Time Complexity:
The time complexity of this algorithm is O(N * (2 N)), where 'N' represents the total number of elements in the 'ARRAY' data structure.
The external loop goes through 'N' iterations, and for each 'i' iteration of the outer loop, the internal loop goes through 2i iterations. During this process, we replicate the list, which has a maximum length of N, at the conclusion of each subset.
As a consequence, the overall time complexity will amount to N (2 0 + 2 1 +. . . + 2 N-2 + 2 N-1 ) = O(N 2 N ).
Space Complexity: O(1).
There is no extra space required.
Method 2: Recursive Approach
We will create a recursive function called solve to generate subsets using this approach.
The following four parameters will be provided to the recursive function :
- We must find the power set of an array called 'ARRAY' .
- The current element's index in the ARRAY array is 'IDX' (originally zero).
- The present array is designated as 'CURRENT' and will hold a subset.
- 'ANSWER' is an array of arrays storing our final response.
We face a choice at every stage: either include the element in the chosen subset. Moreover, if the index of the currently selected element exceeds or equals the size of the provided array, the recursive function will stop.
Condition of Origin:
If IDX is greater than or equal to the size of ANSWER, then add 'CURRENT' to ANSWER and exit the function.
Recursive Calls:
- Execute the recursive function by increasing the 'IDX' value by 1 and replacing the array 'ARRAY' with the excluding current element.
- Push the 'ARRAY[IDX]' to 'CURRENT' .
- Call the recursive function that increases the 'IDX' value by one and populates the array 'ARRAY' with the currently selected element.
Now, let's examine the algorithm's source code.
Filename: Power_set.c
#include<iostream>
#include<vector>
using namespace std;
void solve(int idx, vector<int> &array, vector<int> current, vector<vector<int>> &answer)
{
//condition
if (idx >= array.size())
{
answer.push_back(current);
return;
}
//The recursive function call
solve(idx + 1, array, current, answer);
current.push_back(array[idx]);
solve(idx + 1, array, current, answer);
}
vector<vector<int>> powerSet(vector<int> array)
{
//To hold all subsets, create a collection of arrays.
vector<vector<int>> answer;
vector <int> current;
int idx = 0;
solve(idx, array, current, answer);
// returning the answer array
return answer;
}
int main()
{
// user input
int number;
cin>>number;
vector<int> array(number, 0);
for(int i = 0; i < number; i++)
cin >> array[i];
//Using the powerSet() function to construct the 'ARRAY' power set.
vector<vector<int>> answer = powerSet(array);
// displaying the power set
for(int i = 0; i < answer.size(); i++){
for(int j = 0; j < answer[i].size(); j++)
cout << answer[i][j] << " ";
cout << endl;
}
}
Input:
3
1 2 3
Output:
3
2
2 3
1
1 3
1 2
1 2 3
Complexity:
Time Complexity:
O(2^N), where 'N' is the array length, 'ARR' .
Just like in recursive functions, we initiate two calls at every step which leads to a total of 2^N calls. Consequently, the overall time complexity amounts to O(2^N).
Space complexity:
In O(N) time complexity, 'N' represents the size of the array and 'ARRAY' denotes the array's length.
The Recursion tree's depth can reach 'N' in the worst-case scenario, leading to a space complexity of O(N) for the recursive call stack.
Method 3: The Bitmask Method
We can employ a binary digit to signify if the linked element belongs to the present subset, as it can be either 0 or 1. Consequently, each bit in the sequence denotes a subset within the complete set. This approach enables us to generate all subsets without requiring additional storage capacity.
Assume we have the 'ARRAY' array.
Assume our response is 'ANSWER' = [].
Iterate 0<= I<= 2^N times and perform the following:
- Consider the following array: TEMP =
- Iterate through ARRAY[i] for each 0 = j N and do the following:
- Add the 'j'th value to 'TEMP' if the 'j'th bit of 'i' is set.
- 'TEMP' should be added at the end of 'ANSWER' .
Filename: Powerset3.cpp
#include<iostream>
#include<vector>
using namespace std;
vector<vector<int>> powerSet(vector<int> &array)
{
int number = array.size();
//an array for storing all the subsets
vector<vector<int>> answer;
for (int i = 0; i < (1<<number); i++)
{
vector<int> tem;
// iterating over the array
for (int j = 0; j < number; j++)
{
// checking the jth bit
if (i & (1 << j))
{
tem.push_back(array[j]);
}
}
answer.push_back(tem);
}
// Return the ?ANSWER?.
return answer;
}
int main()
{
// user input
int number;
cin >> number;
vector<int> array(number, 0);
for(int i = 0; i < number; i++)
cin >> array[i];
// function calling.
vector<vector<int>> answer = powerSet(array);
//The display of the power set
for (int i = 0; i < answer.size(); i++) {
for (int j = 0; j < answer[i].size(); j++)
cout << answer[i][j] << " ";
cout << endl;
}
}
Input:
3
1 2 3
Output:
1
2
1 2
3
1 3
2 3
1 2 3
