Count of subsequences having maximum distinct elements

https://www.geeksforgeeks.org/count-subsequences-maximum-distinct-elements/

Given an arr of size n. The problem is to count all the subsequences having maximum number of distinct elements.

Examples:

Input : arr[] = {4, 7, 6, 7}
Output : 2
The indexes for the subsequences are:
{0, 1, 2} - Subsequence is {4, 7, 6} and
{0, 2, 3} - Subsequence is {4, 6, 7}

Efficient Approach: Create a hash table to store the frequency of each element of the array. Take product of all the frequencies.
The solution is based on the fact that there is always 1 subsequence possible when all elements are distinct. If elements repeat, every occurrence of repeating element makes a mew subsequence of distinct elements

ull countSubseq(int arr[], int n)

{

    // unordered_map 'um' implemented as

    // hash table

    unordered_map<int, int> um;

  

    ull count = 1;

  

    // count frequency of each element

    for (int i = 0; i < n; i++)

        um[arr[i]]++;

  

    // traverse 'um'

    for (auto itr = um.begin(); itr != um.end(); itr++)

  

        // multiply frequency of each element

        // and accumulate it in 'count'

        count *= (itr->second);

  

    // required number of subsequences

    return count;

}