Distinct Subsets Count

Posted: 9 Oct, 2020
Difficulty: Moderate

PROBLEM STATEMENT

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.

Note:
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.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
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