Recuento de subconjuntos únicos de un conjunto que tiene elementos repetidos

Dada una array arr[] de tamaño N . La tarea es contar el número de subconjuntos únicos. 

Ejemplos:

Entrada: arr[] = {1, 2, 2}
Salida: 6
Explicación: Total de subconjuntos posibles de este conjunto = 2³= 8. 
Los siguientes son los 8 subconjuntos formados a partir de arr[].
{}, {1}, {2}, {2}, {1, 2}, {1, 2}, {2, 2}, {1, 2, 2}. 
Estos son todos los subconjuntos posibles de los cuales se repiten {2} y {1, 2}.
Por lo tanto, solo hay 6 subconjuntos únicos del conjunto dado.

Entrada: arr[] ={1, 3, 3, 4, 4, 4}
Salida: 24

Enfoque ingenuo: en el enfoque básico, cree todos los subconjuntos del conjunto y siga almacenándolos en un std::set que almacena solo elementos únicos. Pero este no es un enfoque eficiente en el tiempo. 

Complejidad de Tiempo: O(2 ^N )
Espacio Auxiliar: O(N * 2 ^N-1 )

Enfoque Eficiente: Se puede observar que no se requiere encontrar todos los subconjuntos. La única preocupación es encontrar el recuento de subconjuntos únicos. Sobre la base de cuántas veces contribuye cada elemento en subconjuntos únicos, se puede hacer mediante manipulaciones matemáticas y finalmente terminar con una fórmula.

Siga la observación a continuación para llegar a la fórmula.

Para cada valor único val digo _que la frecuencia de ese elemento es freq[val _i ] .
Entonces, cada valor único tiene (freq[val _i ] + 1) para estar presente en un subconjunto único
porque puede estar presente 0 veces, 1 vez, 2 veces. . . freq[val _i ] veces en un subconjunto.
Ahora bien, esto es cierto para todos esos elementos únicos.
Por lo tanto, El número de subconjuntos únicos de un conjunto = Producto de (frecuencia+1) de cada elemento .

A continuación se muestra la implementación del enfoque anterior.

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find number of unique subsets
void countNumberofUniqueSubsets(int A[],
                                int N)
{
    // Creating a map to store
    // frequency of elements
    map<int, int> m;
 
    // Filling map
    for (int i = 0; i < N; i++) {
        // Counting frequency of each elements
        m[A[i]]++;
    }
 
    // Finding product of (frequency+1)
    // for each elements
    int subsets = 1;
 
    for (auto& value : m)
        subsets *= (value.second + 1);
 
    cout << subsets;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 2 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    countNumberofUniqueSubsets(arr, N);
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
  // Function to find number of unique subsets
  static void countNumberofUniqueSubsets(int A[],
                                         int N)
  {
     
    // Creating a map to store
    // frequency of elements
    HashMap<Integer, Integer> m = new HashMap<>();
 
    // Filling map
    for (int i = 0; i < N; i++) {
      // Counting frequency of each elements
      if (m.containsKey(A[i]))
      {
        m.put(A[i], m.get(A[i]) + 1);
      }
      else
      {
        m.put(A[i], 1);
      }
    }
 
    // Finding product of (frequency+1)
    // for each elements
    int subsets = 1;
 
    for (Map.Entry<Integer, Integer> value : m.entrySet())
      subsets *= (value.getValue() + 1);
 
    System.out.print(subsets);
  }
 
  // Driver Code
  public static void main (String[] args) {
    int arr[] = { 1, 2, 2 };
    int N = arr.length;
 
    // Function Call
    countNumberofUniqueSubsets(arr, N);
  }
}
 
// This code is contributed by hrithikgarg03188.

# Python code for the above approach
 
# Function to find number of unique subsets
def countNumberofUniqueSubsets(A, N):
 
    # Creating a map to store
    # frequency of elements
    m = dict()
 
    # Filling map
    for i in range(N):
 
        # Counting frequency of each elements
        if (A[i] in m):
            m[A[i]] += 1
        else:
            m[A[i]] = 1
 
    # Finding product of (frequency+1)
    # for each elements
    subsets = 1
 
    for value in m.values():
        subsets = subsets * (value + 1)
 
    print(subsets)
 
# Driver Code
arr = [1, 2, 2]
N = len(arr)
 
# Function Call
countNumberofUniqueSubsets(arr, N)
 
# This code is contributed by Saurabh Jaiswal

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
 
  // Function to find number of unique subsets
  static void countNumberofUniqueSubsets(int []A, int N)
  {
 
    // Creating a map to store
    // frequency of elements
    Dictionary<int, int> m =
      new Dictionary<int, int>();
 
    // Filling map
    for (int i = 0; i < N; i++)
    {
 
      // Counting frequency of each elements
      if (m.ContainsKey(A[i]))
      {
        m[A[i]] = m[A[i]] + 1;
      }
      else
      {
        m.Add(A[i], 1);
      }
    }
 
    // Finding product of (frequency+1)
    // for each elements
    int subsets = 1;
 
    foreach(KeyValuePair<int, int> value in m)
    {
      subsets *= (value.Value + 1);
    }
 
    Console.Write(subsets);
  }
 
  // Driver Code
  public static void Main () {
    int []arr = { 1, 2, 2 };
    int N = arr.Length;
 
    // Function Call
    countNumberofUniqueSubsets(arr, N);
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
        // JavaScript code for the above approach
 
        // Function to find number of unique subsets
        function countNumberofUniqueSubsets(A, N)
        {
         
            // Creating a map to store
            // frequency of elements
            let m = new Map();
 
            // Filling map
            for (let i = 0; i < N; i++)
            {
             
                // Counting frequency of each elements
                if (m.has(A[i])) {
                    m.set(A[i], m.get(A[i])+ 1)
                }
                else {
                    m.set(A[i], 1)
                }
            }
 
            // Finding product of (frequency+1)
            // for each elements
            let subsets = 1;
 
            for (let value of m.values())
                subsets = subsets * (value + 1);
 
            document.write(subsets);
        }
 
        // Driver Code
        let arr = [1, 2, 2];
        let N = arr.length;
 
        // Function Call
        countNumberofUniqueSubsets(arr, N);
 
       // This code is contributed by Potta Lokesh
    </script>

6

Complejidad temporal: O(N)
Espacio auxiliar: O(N)