Subsets II

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.

In this approach, we will define a recursive function REC(‘st’,’ CUR’, ’ARR’, ’SUBSETS’) that will recursively build the subsets and store them into ‘SUBSETS’ array. For each call of REC(), we will check if the element is duplicate or not. If not, we will make a recursive call by include the ith element into the ‘CUR’ subset and make a recursive call for st as i+1 and then pop out the element after the recursive call to backtrack.

At last, we will return the ‘SUBSETS’ array.

Algorithm:

• Declare REC(st,’CUR’, ‘ARR’,SUBSETS’) that will recursively generate the unique subsets:
  • Insert ‘CUR’ into ‘SUBSETS’.
  • For i in range st to len(ARR)-1:
    • If i is equal to st or ARR[i] is not equal to ARR[i-1]:
      • Append ARR[i] into ‘CUR’.
      • Call REC(i+1,CUR,ARR,SUBSETS).
      • Pop-back ARR[i] from CUR (Backtracking).
• Declare a variable array of arrays  ‘SUBSETS’  to store the subsets.
• Sort the given array ‘ARR’.
• Declare an empty array ‘CUR’.
• Call REC(0, CUR, ARR, SUBSETS).
• Return ‘SUBSETS’.

In this approach, we will iterate the mask from 0 to 2^N and observe its binary representation. If the ith bis are set, it implies ARR[i] is included in the current subset and we will also check if including this element forms a duplicate set. If not we will include the current subset into the ‘SUBSETS’ array.

For eg: if suppose we have array : [ 1, 2, 3, 4] and 'mask' = 5(0101) then 'CUR' represent a set which contains element ['2', '4'].

We run this process for ‘MASK’ equal to 0 to 2^N -1 so that all the possible subsets are checked.

Algorithm:

• Declare a variable array of arrays  ‘SUBSETS’  to store the subsets.
• Sort the given array ‘ARR’.
• Declare an empty array ‘CUR’.
• For ‘MASK’ in range 0 to (2^N-1), do the following:
  • Set ‘CUR’ as an empty array.
  • Set ‘UNIQUE’ as true.
  • For i in range 0 to N-1:
    • If ( MASK & 1<<i) is equal to 0:
      • If implies ith bit is not set.
      • Continue.
    • If i>0 and ARR[i] == ARR[i-1] and (MASK & 1<<(i-1) ) == 0:
      • Set ‘UNIQUE’ as False.
    • If UNIQUE is  False:
      • Break.
    • Insert ARR[i] into ‘CUR’.
  • If UNIQUE is true:
    • Insert ‘CUR’ into ‘SUBSETS’.
• Return ‘SUBSETS’.