Find All Subsets

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
33 upvotes
Asked in companies
Flipkart limitedUnthinkable SolutionsMicrofocus

Problem statement

You are given an array 'arr' of 'N' distinct integers. Your task is to find all the non-empty subsets of the array.


Note: You can return the subsets in any order, you don’t have to specifically sort them.


Example: 
arr=[3,4,5]
subsets ={3}, {3,4}, {3,4,5}, {3,5}, {4}, {4,5}, {5}
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integers ‘N’ denoting the length of the array.

The second line contains ‘N’ integers denoting the array elements.
Output Format : 
The output contains each subset in a separate line.
Note:- 
You don’t need to print anything. Just implement the given function.
Sample Input 1 :
3
1 2 3
Sample Output 1 :
1
1 2
1 2 3
1 3
2
2 3
3
Explanation Of Sample Output 1 :
Total 7 possible subsets can be formed: {1}, {1,2}, {1,2,3}, {1,3}, {2}, {2,3}, {3}
Sample Input 2 :
2
1 2
Sample Output 2 :
1 
1 2 
2
Constraints :
1 <= N <= 10
-10^9 <= arr[i] <= 10^9

Time limit: 1 sec
Hint

We need to find the power set of the given array.

Approaches (2)
Power Set Using Bit-Masking

 

One of the standard and useful method of finding the power set is through bit-masking.

Consider a number with N-bits in its binary representation, if we consider that the state of ith bit depicts whether the ith array element is included in the current subset or not, then we can uniquely identify one of the subsets (as each number has a different binary representation).

Now we can simply iterate from 1 to 2n-1, each number in this iteration will define a subset uniquely. To generate the subset just check for the bits that are ON in binary representation on the number, and for each ON bit, we will simply include an array element corresponding to its position.

Remember to not include an empty subset in the final answer.

 

The steps are as follows :

  1. Declare a 2-D container ans to store all the subsets
  2. Run a for loop for num from 1 to 2^N -1
  3. Run inner for loop for i from 0 to N-1
  4. If the ith bit in num has value equal to 1 then include ith element of the array in the current subset.
  5. Push each subset generated into ans
  6. Finally, return ans
Time Complexity

O( N * 2^N ), where N is the size of the input array.

 

We iterate through N bits for each of the 2^N-1 numbers. Hence the time complexity is O(N * 2^N) 

Space Complexity

O( N * 2^N ), where N is the size of the input array.

 

Since a total of 2^N-1 subsets are generated, and maximum possible length of each subset is of order N . Hence the space complexity is O(N * 2^N).

Code Solution
(100% EXP penalty)
Find All Subsets
Full screen
Console