# Distinct Subsets Count

Posted: 9 Oct, 2020
Difficulty: Moderate

## PROBLEM STATEMENT

#### 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.