Encuentre todos los subconjuntos únicos de un conjunto dado usando C++ STL

Dada una array arr[] de números enteros de tamaño N que pueden contener duplicados, la tarea es encontrar todos los subconjuntos únicos posibles, utilizando C++ STL .

Nota: Cada subconjunto debe estar ordenado.

Ejemplos:

Entrada : N = 3, arr[] = {2, 1, 2}
Salida :(), (1), (1 2), (1 2 2), (2), (2 2)
Explicación:  Todos los subconjuntos posibles =(), (2), (1), (1, 2), (2), (2 2), (2 1), (2, 1, 2)
Después de ordenar cada subconjunto =(), (2) , (1), (1, 2), (2), (2, 2), (1, 2), (1, 2, 2) 
Subconjuntos únicos en orden lexicográfico =(), (1), (1, 2), (1, 2, 2), (2), (2, 2)

Entrada: N = 4, arr[] = {1, 2, 3, 3}
Salida:(), (1), (1 2), (1 2 3)
(1 2 3 3), (1 3), (1 3 3), (2), (2 3)
(2 3 3), (3), (3 3)

Enfoque: este problema se puede resolver usando C++ STL Set y recursividad según la siguiente idea:

Intente empujar todos los subconjuntos posibles en el conjunto recursivamente siguiendo las condiciones a continuación

• elija el elemento y empújelo al contenedor y muévase al siguiente elemento
• o no seleccione el elemento y muévase a la siguiente posición

Siga los pasos para resolver el problema:

• Crea un conjunto de vectores para almacenar nuestra respuesta.
• Ordene la array dada ya que la necesidad es obtener subconjuntos en orden ordenado.
• Ahora inserte recursivamente todos los subconjuntos posibles en el conjunto siguiendo el siguiente enfoque para cada i ^-ésimo elemento en la array dada
  • Elija el elemento y empújelo hacia el vector y muévalo a la posición i + 1
  • o no elija y muévase a la posición i+1
• Después de completar el proceso anterior, el conjunto contendrá los subconjuntos necesarios. Ahora simplemente inserte todos los vectores del conjunto en otro vector de vectores y devuélvalo como resultado.

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

// C++ code for the above approach:
  
#include <bits/stdc++.h>
using namespace std;
  
void solve(vector<int>& arr, int n,
           set<vector<int> >& ans,
           vector<int> v, int i)
{
    if (i >= n) {
        ans.insert(v);
        return;
    }
  
    // Not pick
    solve(arr, n, ans, v, i + 1);
  
    // Pick
    v.push_back(arr[i]);
    solve(arr, n, ans, v, i + 1);
}
  
vector<vector<int> > AllSubsets(
    vector<int> arr, int n)
{
  
    // Set of vectors to store
    // required unique subsets
    set<vector<int> > ans;
  
    sort(arr.begin(), arr.end());
    vector<int> v;
    solve(arr, n, ans, v, 0);
  
    // Vector of vectors to store final result
    vector<vector<int> > res;
    while (!ans.empty()) {
        res.push_back(*ans.begin());
        ans.erase(ans.begin());
    }
    return res;
}
  
// Print Function
void print(int N, vector<int>& A)
{
    vector<vector<int> > result = AllSubsets(A, N);
  
    // printing the output
    for (int i = 0; i < result.size(); i++) {
        cout << '(';
        for (int j = 0; j < result[i].size(); j++) {
            cout << result[i][j];
            if (j < result[i].size() - 1)
                cout << " ";
        }
        cout << "), ";
    }
    cout << "\n";
}
  
// Drivers code
int main()
{
    int N = 3;
    vector<int> A = { 2, 1, 2 };
  
    // Function Call
    print(N, A);
    return 0;
}

(), (1), (1 2), (1 2 2), (2), (2 2), 

Complejidad Temporal: O(2 ^N )
Espacio Auxiliar:   O(2 ^N * X), ​​donde X = Longitud de cada subconjunto.