Distinct Subsets Count
Posted: 9 Oct, 2020
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.
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.
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
- 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.
Lexicographic Permutation Rank
Posted: 13 Jul, 2021
Zero Pair Sum
Posted: 22 Jul, 2021
Implement a Queue
Posted: 27 Jul, 2021
Remove K Corner Elements
Posted: 31 Jul, 2021
Posted: 12 Nov, 2021