Problem of the day
You are given an array ‘arr’ of ‘N’ distinct integers. Your task is to print all the non-empty subsets of the array.
Note: elements inside each subset should be sorted in increasing order. But you can print the subsets in any order, you don’t have to specifically sort them.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows
The first line of each test case contains a single integers ‘N’ denoting the length of the array.
The second line of each test case contains ‘N’ integers denoting the array elements.
Output Format :
For each test case print each subset in a separate line.
The subsets can be print in any order.
Output for each test case will be printed in a separate line.
1 <= T <= 10
1 <= N <= 10
10^-9 <= arr[i] <= 10^9
Time limit: 1 sec
2
3
1 2 3
1
10
1
1 2
1 2 3
1 3
2
2 3
3
10
For test case 1 :
Total 7 possible subsets can be formed: {1}, {1,2}, {1,2,3}, {1,3}, {2}, {2,3}, {3}
For test case 2 :
Only a single subset {10} is possible for the given input array.
2
2
1 2
3
1 2 3
1
1 2
2
1
1 2
1 2 3
1 3
2
2 3
3
We need to find the power set of the given array.
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 :
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)
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).