Operations on arrays is an important area to master when it comes to programming. Finding the power set in an array is one such frequently asked question in coding interviews. You can practice the question at the Coding Ninjas Studio and return to this blog if you feel stuck.
A collection of unique elements is referred to as a set. A set with no elements is called an empty set, and a power set is defined as a set of all the subsets that are possible of a given set, which in our case is an array.
We have been given an array of 'N' integers. We have to create a power set for this array, with each subset of the power set being sorted separately.
The array of subsets must be returned. The subset's members should be ARRanged in ascending order. The order of the subsets in the answer array does not matter.
Now, let’s understand this by the following example.
Let’s say we have the set [1,2,3]
Different subsets of the given set are
[ ], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]
Now the power set would be simply the set containing all these subsets. Thus our answer is
With the example below, we can see how the strategy works.
We've set N to 3 and given the input array = [1,2,3].
Initially, we have [ [ ] ]
Now we will create two copies of previous subsets, and add 1 to each of the copies: [ [ ], [1] ]
Again, we will create two copies of previous subsets, and add 2 to each of the copies : [ [ ], [1], [2], [1, 2] ]
Again, we will create two copies of previous subsets, and add 3 to each of the copies : [ [ ], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
Lets look at the implementation of the above algorithm.
Program
#include<iostream>
#include<vector>
using namespace std;
vector<vector<int>> powerSet(vector<int> &arr)
{
int n = arr.size();
// Create an array of arrays to store all subsets.
vector<vector<int>> ans = {{}};
// Traverse through the array 'ARR'.
for (int i = 0; i < n; i++)
{
int element = arr[i];
int len = ans.size();
// Traverse through the array 'ANS' from 0 to 'LEN' index.
for (int j = 0; j < len; j++)
{
vector<int> temp = ans[j];
// Include element in the subset ‘TEMP’.
temp.push_back(element);
ans.push_back(temp);
}
}
// Return the array ‘ANS’.
return ans;
}
int main()
{
// Taking user input.
int n;
cin>>n;
vector<int> arr(n, 0);
for(int i = 0; i < n; i++)
cin >> arr[i];
// Calling powerSet() function to generate the power set of 'ARR'.
vector<vector<int>> ans = powerSet(arr);
// Printing the power set.
for(int i = 0; i < ans.size(); i++){
for(int j = 0; j < ans[i].size(); j++)
cout << ans[i][j] << " ";
cout << endl;
}
}
You can also try this code with Online C++ Compiler
O(N * (2 ^ N)), where ‘N’ is the size of the array, ‘ARR’.
The outer loop runs ‘N’ times, and for every iteration, ‘i’ of the outer loop, the inner loop runs 2i times, within which we copy the list of length at most N at the end of every subset.
So the overall time complexity will be N * (20 + 21 +. . . + 2N-2 + 2N-1) = O(N * 2N).
In this approach, we'll create a recursive function(solve) to generate the subsets.
Four parameters will be passed to the recursive function:
Given array as ‘ARR’ whose power set, we have to find.
The index of the current element in the array ‘ARR’ as ‘IDX’ (initially zero’.
The current array as ‘CURR’, which will hold a subset till now.
An array of arrays, ‘ANS’ that will hold our final answer.
Now we have two options at each step: add the element to the current subset or not. Also, when the index of the current element is greater than or equal to the size of the specified array, the recursive function will terminate.
Condition of Origin:
If IDX >=ANS.size(), then push ‘CURR’ to ‘ANS’ and return.
Recursive Calls:
Call the recursive function by increasing the ‘IDX’ value by one and array ‘ARR’ with the excluded current element.
Push the ‘ARR[IDX]’ to ‘CURR’.
Call the recursive function by increasing the ‘IDX’ value by one and array ‘ARR’ with included current element.
Now let us look at the code for the above algorithm.
Program
#include<iostream>
#include<vector>
using namespace std;
void solve(int idx, vector<int> &arr, vector<int> curr, vector<vector<int>> &ans)
{
// Base condition.
if (idx >= arr.size())
{
ans.push_back(curr);
return;
}
// Recursive call to exclude ‘ARR[IDX]’ from the subset.
solve(idx + 1, arr, curr, ans);
// Recursive call to include ‘ARR[IDX]’ in the subset.
curr.push_back(arr[idx]);
solve(idx + 1, arr, curr, ans);
}
vector<vector<int>> powerSet(vector<int> arr)
{
// Create an array of arrays to store all subsets.
vector<vector<int>> ans;
vector <int> curr;
int idx = 0;
solve(idx, arr, curr, ans);
// Return the array ‘ANS’.
return ans;
}
int main()
{
// Taking user input.
int n;
cin>>n;
vector<int> arr(n, 0);
for(int i = 0; i < n; i++)
cin >> arr[i];
// Calling powerSet() function to generate the power set of 'ARR'.
vector<vector<int>> ans = powerSet(arr);
// Printing the power set.
for(int i = 0; i < ans.size(); i++){
for(int j = 0; j < ans[i].size(); j++)
cout << ans[i][j] << " ";
cout << endl;
}
}
You can also try this code with Online C++ Compiler
O(2 ^ N), where ‘N’ is the length of the array, ‘ARR’.
As in the recursion function, at each step, we are making two calls so total calls are 2^N. Hence, the overall time complexity is O(2^N).
Space complexity
O(N),where ‘N’ is the size of the array, ‘ARR’
In the worst case, the depth of the Recursion tree would be ‘N’. Hence, the overall space complexity due to the recursion call stack is O(N).
Bitmask Approach
Till now, it is very apparent that we have two options: picking a number from a subset or not.
Because a bit can be either 0 or 1, we can use it to indicate whether or not the corresponding element is part of the current subset. As a result, each bit pattern will represent a subset of the total. In this way, we can acquire all of the subsets without any extra space.
Suppose we have the ‘ARR’ array.
Let's say our answer is ‘ANS’ = [ [ ] ].
Iterate 0 <= i <= 2 ^ N and do the following:
Take an array, TEMP = [ ]
Iterate over ARR[i] for each 0 <= j < N and perform the following:
If the ‘j’th bit of ‘i’ is set, add the ‘j’th element to ‘TEMP’.
Add ‘TEMP’ to the end of ‘ANS’.
Below is the code for the above implementation.
Program
#include<iostream>
#include<vector>
using namespace std;
vector<vector<int>> powerSet(vector<int> &arr)
{
int n = arr.size();
// Create an array of arrays to store all subsets.
vector<vector<int>> ans;
for (int i = 0; i < pow(2, n); i++)
{
vector<int> temp;
// Traverse through the array ‘ARR’.
for (int j = 0; j < n; j++)
{
// Check if j-th bit of i is set.
if (i & (1 << j))
{
temp.push_back(arr[j]);
}
}
// Insert the subset ‘TEMP’ in ‘ANS’.
ans.push_back(temp);
}
// Return the ‘ANS’.
return ans;
}
int main()
{
// Taking user input.
int n;
cin >> n;
vector<int> arr(n, 0);
for(int i = 0; i < n; i++)
cin >> arr[i];
// Calling powerSet() function to generate the power set of 'ARR'.
vector<vector<int>> ans = powerSet(arr);
// Printing the power set.
for (int i = 0; i < ans.size(); i++) {
for (int j = 0; j < ans[i].size(); j++)
cout << ans[i][j] << " ";
cout << endl;
}
}
You can also try this code with Online C++ Compiler
O(N * (2 ^ N)), where ‘N’ is the size of the array.
As we are traversing from 0 to 2 ^ N using the outer for loop. Along with this in each iteration also traversing the whole array of size N. So, the overall time complexity is O(N * (2 ^ N)).
Space Complexity
O(1).
As no extra space is used.
Key Takeaways
Now, you have understood how to find the power set of a given array. We saw all the possible approaches and finally generated a set of all the subsets, i.e., power set. You must be thrilled about learning a new question. But learning never stops, and a good coder should never stop practicing. So head over to our practice platform Coding Ninjas Studio to practice top problems and many more. Till then, Happy Coding!
8+ registered 