Distinct Subsets Count

Posted: 9 Oct, 2020
Difficulty: Moderate


Try Problem

Given an array arr of N integers that may contain duplicate integers. The task is to return the count of subsets of the given array such that each subset contains only distinct elements.

As the answer can be large, return your answer modulo 10^9  + 7. 
Input format:
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first line of each test case or query contains an integer 'N' representing the size of the array (arr).

The second line contains 'N' single space-separated integers, representing the elements in the array.
Output format:
For each test case, print the count of subsets modulo 10^9+7 in a separate line.
You do not need to print anything, it has already been taken care of. Just implement the given function.
1 <= T <= 10 
1 <= N <= 10^5 
1 <= arr[i] <= 10^5 

Time limit: 1 second
Approach 1
  • The idea is to call a helper function so as to create all possible subsets of the array.
    • vector<int> current = the vector storing the current possible subset of the array.
    • Recursive calls for generating all possible subsets.
  • We maintain a count variable to count the subsets which have no duplicate elements. Thus, in addition to the base case, we maintain a map so as to check if the frequency of any element exceeds 1.
  • We return the count of distinct subsets received from the helper function.
Try Problem