Dada una array A[] de enteros positivos, imprima todos los subconjuntos únicos no vacíos de la array
Nota: el conjunto no puede contener elementos duplicados, por lo que cualquier subconjunto repetido debe considerarse solo una vez en la salida.
Ejemplos:
Entrada: A[] = {1, 5, 6}
Salida: {{1}, {1, 5}, {1, 6}, {5}, {5, 6}, {6}, {1, 5 , 6}}
Explicación: El número de todos los subconjuntos posibles no vacíos será 2 N-1 .
Aquí serán {1}, {1, 5}, {1, 6}, {5}, {5, 6}, {6} y {1, 5, 6}Entrada: A[] = {1, 2, 2}
Salida: {{1}, {1, 2}, {1, 2, 2}, {2}, {2, 2}}
Intuición: La idea principal para resolver el problema es la siguiente:
Este problema cae bajo el clásico algoritmo de “ elegir o no elegir ”.
En este problema, hay dos opciones de si queremos incluir un elemento en el conjunto o excluirlo. Para cada elección, el elemento se puede agregar a la array resultante y luego, usando el retroceso , lo excluiremos. De esta forma, se generará el conjunto deseado.
La imagen que se muestra a continuación muestra las opciones para cada elemento y cómo se genera la array resultante al final del árbol de recurrencia.
Árbol de recursión para generar todos los subconjuntos
Enfoque 1 (Recursión):
Siga los pasos dados para resolver el problema utilizando el enfoque anterior:
- Iterar sobre los elementos uno por uno.
- Para cada elemento, simplemente elija el elemento y avance recursivamente y agregue el subconjunto al resultado.
- Luego, usando backtracking , elimine el elemento y continúe encontrando los subconjuntos y agregándolos al resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Helper function to find all unique subsets
void findSubsets(vector<int>& v, int idx,
vector<int>& subset,
set<vector<int> >& result)
{
// If the current subset is not empty
// insert it into the result
if (!subset.empty())
result.insert(subset);
// Iterate over every element in the array
for (int j = idx; j < v.size(); j++) {
// Pick the element and move ahead
subset.push_back(v[j]);
findSubsets(v, j + 1, subset, result);
// Backtrack to drop the element
subset.pop_back();
}
}
// Function to return all unique subsets
vector<vector<int> > solve(vector<int>& v)
{
// To store the resulting subsets
set<vector<int> > result;
vector<int> subset;
// Helper function call
findSubsets(v, 0, subset, result);
vector<vector<int> > res;
for (auto v : result)
res.push_back(v);
return res;
}
// Driver code
int main()
{
vector<int> A = { 1, 2, 2 };
// Function call
vector<vector<int> > result = solve(A);
// Print all unique subsets
for (auto v : result) {
for (int i : v) {
cout << i << " ";
}
cout << "\n";
}
return 0;
}
Java
// Java code to implement the above approach
import java.io.*;
import java.util.*;
class GFG {
// Helper function to find all unique subsets
static void findSubsets(List<Integer> v, int idx,
List<Integer> subset,
List<List<Integer> > result)
{
// If the current subset is not empty insert it into
// the result
if (!subset.isEmpty()) {
if (!result.contains(subset)) {
result.add(new ArrayList<>(subset));
}
}
// Iterate over every element in the array
for (int j = idx; j < v.size(); j++) {
// Pick the element and move ahead
subset.add(v.get(j));
findSubsets(v, j + 1, subset, result);
// Backtrack to drop the element
subset.remove(subset.size() - 1);
}
}
// Function to return all unique subsets
static List<List<Integer> > solve(List<Integer> v)
{
// To store the resulting subsets.
List<List<Integer> > result
= new ArrayList<List<Integer> >();
List<Integer> subset = new ArrayList<Integer>();
// Helper function call
findSubsets(v, 0, subset, result);
List<List<Integer> > res
= new ArrayList<List<Integer> >();
for (int i = 0; i < result.size(); i++) {
res.add(new ArrayList<>(result.get(i)));
}
return res;
}
public static void main(String[] args)
{
List<Integer> A = new ArrayList<Integer>();
A.add(1);
A.add(2);
A.add(2);
List<List<Integer> > result
= new ArrayList<List<Integer> >();
// Function call
result = solve(A);
// print all unique subsets
for (int i = 0; i < result.size(); i++) {
List<Integer> temp = result.get(i);
for (int j = 0; j < temp.size(); j++) {
System.out.print(temp.get(j) + " ");
}
System.out.println();
}
}
}
// This code is contributed by lokesh (lokeshmvs21).
1 1 2 1 2 2 2 2 2
Complejidad del tiempo: O(N * log(2 N ) * 2 N ) = O(N 2 * 2 N )
Espacio auxiliar: O(2 N )
Enfoque 2 (Enfoque iterativo):
Siga los pasos dados para resolver el problema utilizando el enfoque anterior:
- Iterar a través de cada número, y hay dos opciones:
- Incluya el elemento y luego agréguelo a todos los subconjuntos.
- O excluya el elemento, luego no haga nada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return all unique subsets
vector<vector<int> > solve(vector<int>& v)
{
// To store the resulting subsets
set<vector<int> > res;
vector<int> subset;
vector<vector<int> > result;
// Insert it into the resultant vector
res.insert(subset);
// Iterate over all elements
for (int i = 0; i < v.size(); i++) {
int N = res.size();
for (auto it = res.begin();
it != res.end() and N > 0; it++) {
// Iterate through every subset
// generated till now and inset
// the current element in the
// end of it
subset = *it;
subset.push_back(v[i]);
result.push_back(subset);
N--;
}
res.insert(result.begin(), result.end());
result.clear();
}
for (auto u : res)
result.push_back(u);
return result;
}
// Driver code
int main()
{
vector<int> A = { 1, 2, 2 };
// Function call
vector<vector<int> > result = solve(A);
for (auto v : result) {
for (int i : v) {
cout << i << " ";
}
cout << "\n";
}
return 0;
}
1 1 2 1 2 2 2 2 2
Complejidad temporal: O(N 2 * 2 N )
Espacio auxiliar: O(2 N )
Enfoque 3 (Bit Masking):
Requisito previo: Power Set
Para resolver el problema utilizando el enfoque anterior, siga la siguiente idea:
Representar todos los números del 1 al 2 N – 1 donde N es el tamaño del subconjunto en el formato binario y la posición para la cual los bits están configurados para agregarse a la array y luego agregar esa array al resultado, es decir, usar un patrón de máscara de bits para generar todas las combinaciones. Por ejemplo,
Entrada: A = {1, 5, 6}, N = 3
Explicación: Por lo tanto, comprobaremos todos los números del 1 al 7, es decir, hasta el 2 n-1 = 2 3 – 1 = 7
1 => 001 => {6}
2 = > 010 => {5}
3 => 011 => {5, 6}
4 => 100 => {1}
5 => 101 => {1, 6}
6 => 110 => {1, 5}
7 => 111 => {1, 5, 6}
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the unique subsets
vector<vector<int> > solve(vector<int>& v)
{
// To store the resulting subsets
set<vector<int> > res;
vector<int> subset;
int size = v.size();
// Finding 2^N
int N = 1 << size;
for (int i = 1; i < N; i++) {
int bit = i;
subset.clear();
int pos = 0;
while (bit) {
// If the bit is set inset
// it into the subset
if (bit & 1) {
subset.push_back(v[pos]);
}
pos++;
bit >>= 1;
}
res.insert(subset);
}
vector<vector<int> > result;
for (auto u : res)
result.push_back(u);
return result;
}
// Driver code
int main()
{
vector<int> A = { 1, 2, 2 };
// Function call
vector<vector<int> > result = solve(A);
for (auto v : result) {
for (int i : v) {
cout << i << " ";
}
cout << "\n";
}
return 0;
}
1 1 2 1 2 2 2 2 2
Complejidad de Tiempo: O(N 2 * 2 N )
Espacio Auxiliar: O(2 N )
Publicación traducida automáticamente
Artículo escrito por sahilgangurde08 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA