Recuento de subsecuencias que tienen un máximo de elementos distintos

Dado un arr de tamaño n . El problema es contar todas las subsecuencias que tienen el máximo número de elementos distintos.

Ejemplos: 

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}

Input : arr[] = {9, 6, 4, 4, 5, 9, 6, 1, 2}
Output : 8

Enfoque ingenuo: Considere todas las subsecuencias que tienen elementos distintos y cuente las que tienen el máximo de elementos distintos.

Enfoque eficiente: cree una tabla hash para almacenar la frecuencia de cada elemento de la array. Tomar el producto de todas las frecuencias. 
La solución se basa en el hecho de que siempre hay 1 subsecuencia posible cuando todos los elementos son distintos. Si los elementos se repiten, cada aparición de un elemento repetido crea una nueva subsecuencia de elementos distintos.

Implementación:

// C++ implementation to count subsequences having
// maximum distinct elements
#include <bits/stdc++.h>
using namespace std;
 
typedef unsigned long long int ull;
 
// function to count subsequences having
// maximum 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;
}
 
// Driver program to test above
int main()
{
    int arr[] = { 4, 7, 6, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Count = "
         << countSubseq(arr, n);
    return 0;
}

// Java implementation to count subsequences having
// maximum distinct elements
import java.util.HashMap;
 
class geeks
{
     
    // function to count subsequences having
    // maximum distinct elements
    public static long countSubseq(int[] arr, int n)
    {
 
        // unordered_map 'um' implemented as
        // hash table
        HashMap<Integer, Integer> um = new HashMap<>();
 
        long count = 1;
 
        // count frequency of each element
        for (int i = 0; i < n; i++)
        {
            if (um.get(arr[i]) != null)
            {
                int a = um.get(arr[i]);
                um.put(arr[i], ++a);
            }
            else
                um.put(arr[i], 1);
        }
         
        // traverse 'um'
        for (HashMap.Entry<Integer, Integer> entry : um.entrySet())
        {
             
            // multiply frequency of each element
            // and accumulate it in 'count'
            count *= entry.getValue();
        }
         
        // required number of subsequences
        return count;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 4, 7, 6, 7 };
        int n = arr.length;
        System.out.println("Count = " + countSubseq(arr, n));
    }
}
 
// This code is contributed by
// sanjeev2552

# Python 3 implementation to count subsequences
# having maximum distinct elements
 
# function to count subsequences having
# maximum distinct elements
def countSubseq(arr, n):
     
    # unordered_map 'um' implemented
    # as hash table
    # take range equal to maximum
    # value of arr
    um = {i:0 for i in range(8)}
 
    count = 1
 
    # count frequency of each element
    for i in range(n):
        um[arr[i]] += 1
 
    # traverse 'um'
    for key, values in um.items():
         
        # multiply frequency of each element
        # and accumulate it in 'count'
        if(values > 0):
            count *= values
 
    # required number of subsequences
    return count
 
# Driver Code
if __name__ == '__main__':
    arr = [4, 7, 6, 7]
    n = len(arr)
    print("Count =", countSubseq(arr, n))
 
# This code is contributed by
# Surendra_Gangwar

// C# implementation to count subsequences
// having maximum distinct elements
using System;
using System.Collections.Generic;
     
class GFG
{
     
    // function to count subsequences having
    // maximum distinct elements
    public static long countSubseq(int[] arr,
                                   int n)
    {
 
        // unordered_map 'um' implemented as
        // hash table
        Dictionary<int,
                   int> um = new Dictionary<int,
                                            int>();
 
        long count = 1;
 
        // count frequency of each element
        for (int i = 0; i < n; i++)
        {
            if (um.ContainsKey(arr[i]))
            {
                int a = um[arr[i]];
                um.Remove(arr[i]);
                um.Add(arr[i], ++a);
            }
            else
                um.Add(arr[i], 1);
        }
         
        // traverse 'um'
        foreach(KeyValuePair<int, int> entry in um)
        {
             
            // multiply frequency of each element
            // and accumulate it in 'count'
            count *= entry.Value;
        }
         
        // required number of subsequences
        return count;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int[] arr = { 4, 7, 6, 7 };
        int n = arr.Length;
        Console.WriteLine("Count = " +
                           countSubseq(arr, n));
    }
}
 
// This code is contributed by Princi Singh

<script>
 
// Javascript implementation to count subsequences having
// maximum distinct elements
 
// function to count subsequences having
// maximum distinct elements
function countSubseq(arr, n)
{
 
    // unordered_map 'um' implemented as
    // hash table
    var um = new Map();
 
    var count = 1;
 
    // count frequency of each element
    for (var i = 0; i < n; i++)
    {
        if(um.has(arr[i]))
            um.set(arr[i], um.get(arr[i])+1)
        else
            um.set(arr[i], 1);
    }
 
    // traverse 'um'
    um.forEach((value, key) => {
         
        // multiply frequency of each element
        // and accumulate it in 'count'
        count *= value;
    });
     
    // required number of subsequences
    return count;
}
 
// Driver program to test above
var arr = [4, 7, 6, 7];
var n = arr.length;
document.write( "Count = "
      + countSubseq(arr, n));
 
// This code is contributed by noob2000.
</script>

Producción: 

Count = 2

Complejidad temporal: O(n). 
Espacio Auxiliar: O(n).