Subsets II

Moderate
0/80
Average time to solve is 45m
75 upvotes
Asked in companies
AmazonFacebookApple

Problem statement

Ninja is observing an array of ‘N’ numbers and wants to make as many unique subsets as possible. Can you help the Ninja to find all the unique subsets?

Note: Two subsets are called same if they have same set of elements.For example {3,4,1} and {1,4,3} are not unique subsets.

You are given an array ‘ARR’ having N elements. Your task is to print all unique subsets.

For Example 
For the given if ARR = [1,1,3],the answer will be [ ],[1],[1,1],[1,3],[3],[1,1,3].
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains a single integer ‘N’ denoting the number of elements.
The second line of each test case contains ‘ARR’ array.
Output Format: 
For each test case, print all the subsets in each line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Return the output in sorted format as shown in the sample output.
Constraints: 
1 <= T <= 10
1 <= N <= 20.
1 <= ARR[i] <=100

Time limit: 1 sec
Sample Input 1:
2
3
1 1 3
4
1 3 3 3
Sample Output 1:
1
1 1
1 3
3
1 1 3

1
1 3
1 3 3
1 3 3 3 
3 
3 3
3 3 3
Explanation of sample input 1:
For the first test case,
The unique subsets will be  [ ],[1],[1,1],[1,3],[3],[1,1,3]. 

For the second test case:
The unique subsets will be  [ ],[1,3],[1,3,3],[1,3,3,3],[3],[3,3],[3,3,3].
Sample Input 2:
2
4
5 5 3 5 
3
1 3 5
Sample Output 2:
3 
3 5 
3 5 5 
3 5 5 5 
5 
5 5 
5 5 5 

1 
1 3 
1 3 5 
1 5 
3 
3 5 
5
Hint

Try to remove the duplicate subsets.

Approaches (3)
Iterative Method

If there are N elements in the array, then a total of 2^N subsets are possible as each element have two choices either to include it or not.

How many of them are duplicates?

We can treat the duplicate elements as special elements. For example, if we have duplicate elements (5, 5), instead of treating them as two elements that are duplicate, we can treat it as one special element 5, but this element has more than two choices: you can either NOT put it into the subset, or put ONE 5 into the subset, or put TWO 5s into the subset. 

So if A[i] has a frequency of ‘F’, then there are F+1 choices.

Therefore, we are given an array (a1, a2, a3, ..., an) with each of them appearing (k1, k2, k3, ..., kn) times, the number of subsets is (k1+1)(k2+1)...(kn+1).

 

In this approach,we will first sort the array and find the frequency of each element. If the frequency of element ‘X’ is ‘F’, then we will append no Xs ,1 Xs, 2Xs … F Xs to the end of the already made subsets. We will do the following for all unique elements.

  

Algorithm:

  • Declare a variable array of arrays  ‘SUBSETS’  to store the subsets.
  • Insert an empty array to ‘SUBSETS’.
  • Sort the given array ‘ARR’.
  • Set i as 0.
  • While i is less than ‘N’, do the following:
    • Set ‘C’ as 0 to store the frequency of the element.
    • While i+c < N and ARR[i] is equal to ARR[i+c]:
      • Set ‘C’ as ‘C’+1.
    • Set M as the length of ‘SUBSETS’.
    • For j in range 0 to M-1:
      • Set ‘CUR’ as SUBSETS[j].
      • For k in range 0 to ‘C’:
        • Append ARR[i] to CUR.
        • Insert ‘CUR’ to  ‘SUBSETS’.
    • Set i as i+ count.
  • Return ‘SUBSETS’ list containing all the unique subsets.
Time Complexity

O(2^N ), where ‘N’ is the number of elements in ‘ARR’.

 

In this approach, we are finding all the unique subsets of the given array. If all the elements of the array are distinct, then the total number of subsets will be 2^N. Hence, the overall time complexity is O(2^N)

Space Complexity

O(2^N ), where ‘N’ is the number of elements in ‘ARR’.

 

In this approach, we are storing all the unique subsets in a list and at the worst case, the number of the unique subsets can be 2^N. Hence, the overall space complexity is O(2^N).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Subsets II
Full screen
Console