Last Updated: 31 Dec, 2020

Power Set

Easy

Asked in companies

Solve now

Problem statement

You are given a sorted array of 'N' integers. You have to generate the power set for this array where each subset of this power set is individually sorted.

A set is a well-defined collection of distinct elements. Power set P(ARR) of a set 'ARR' is defined as a set of all possible subsets of 'ARR'.

You have to return the array of subsets. The elements in the subset should be sorted in ascending order. The order of subsets in the array does not matter. Hence there can be more than 1 possible solution for a given array.

For example :

If we are given an array ARR=[1,2,3] then the power set P(ARR) of the set ARR is: [ [], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3] ]

Note :

For every subset 'X' present in power set P(ARR) of set ARR, X must be sorted i.e. in the example above:
P1(ARR) =  [ [], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3] ]
P2(ARR) =  [ [], [1], [1,2,3], [2], [1,2], [3], [1,3], [2,3] ]
P3(ARR) =  [ [], [1], [2], [1,2], [3], [1,3], [2,3], [2,3,1] ]
P1(ARR) and P2(ARR) will be considered correct power sets but P3(ARR) will not be considered correct because there the last subset [2, 3, 1] is not sorted.

Input Format :

The first line contains a number 'N' denoting the size of the array.
The second line contains 'N' space-separated distinct integer denoting the elements of the array.

Output format :

 For each given 'N' print 2^N separate lines each denoting a subset.
 For each subset, print its element separated by space.

Note :

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= N <= 15
1 <= ARR[i] <= 50    
Time limit : 1 second

Solve now

Approaches

01 Approach

We will start with a set of empty subsets and will traverse N time. Each time generating new subsets with the addition of the current element and keeping all the previous subsets. So basically we are doubling the size of the set in each iteration.

We can understand the approach with the below example.

We have given N = 3 and input array =[1,2,3]

Initially, we have [ [] ]
Adding 1 to all previous subsets : [ [] ,[1] ]
Adding 2 to all previous subsets : [ [] ,[1], [2] ,[1,2] ]
Adding 3 to all previous subsets : [ [] ,[1], [2] ,[1,2] ,[3],[1,3] ,[2,3] ,[1,2,3]]

Solve now

02 Approach

We will make a recursive function that will help to generate subsets, at each step we have two choices either add the element to the current subset or not and we will call this recursive function. The terminating condition for the recursive function will be when the index of the element is greater than or equal to the size of the given array.

Let’s say we have a given array ARR.
The recursion function will receive four parameters
1. Given array ARR,
2. Index of current element IDX
3. The current array say CURR,
4. An array of arrays say ANS which will hold the final answer.
Base condition :
1. If IDX> =ANS.size() then push CURR to ANS and return.
Recursive calls :
1. Increase the IDX by 1
2. Call the recursive function.
3. Push the ARR[IDX] to CURR
4. Call the recursive function.

Solve now

03 Approach

So we have two possibilities either selecting a number in subset or not.

A bit can be either 0 or 1, thus we can use this to denote whether the corresponding element belongs to the current subset or not. So each bit pattern will represent a subset. So we will get all the subsets.

Let’s say we have a given array ARR.
Let ANS = [ [] ] is our answer.
Iterate 0<= I <=2^N and do:
1. CURR = []
2. Iterate over ARR[i] for each 0 <= J < N and do:
  1. If the Jth bit is set in I then include the Jth element to CURR.
3. Append CURR to ANS.

Solve now