Encontrar todos los subconjuntos de un conjunto dado en Java

Problema: Encuentra todos los subconjuntos de un conjunto dado.

Input: 
S = {a, b, c, d}
Output:
{}, {a} , {b}, {c}, {d}, {a,b}, {a,c},
{a,d}, {b,c}, {b,d}, {c,d}, {a,b,c}, 
{a,b,d}, {a,c,d}, {b,c,d}, {a,b,c,d}

El número total de subconjuntos de cualquier conjunto dado es igual a 2^ (nº de elementos en el conjunto). Si observamos cuidadosamente, no son más que números binarios del 0 al 15, que se pueden mostrar a continuación: 
 

Comenzando desde la derecha, 1 en la i-ésima posición muestra que el i-ésimo elemento del conjunto está presente mientras que 0 muestra que el elemento está ausente. Por lo tanto, lo que tenemos que hacer es generar los números binarios de 0 a 2^n – 1, donde n es la longitud del conjunto o el número de elementos en el conjunto.

Implementación:

// A Java program to print all subsets of a set
import java.io.IOException;
 
class Main
{
    // Print all subsets of given set[]
    static void printSubsets(char set[])
    {
        int n = set.length;
 
        // Run a loop for printing all 2^n
        // subsets one by one
        for (int i = 0; i < (1<<n); i++)
        {
            System.out.print("{ ");
 
            // Print current subset
            for (int j = 0; j < n; j++)
 
                // (1<<j) is a number with jth bit 1
                // so when we 'and' them with the
                // subset number we get which numbers
                // are present in the subset and which
                // are not
                if ((i & (1 << j)) > 0)
                    System.out.print(set[j] + " ");
 
            System.out.println("}");
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        char set[] = {'a', 'b', 'c'};
        printSubsets(set);
    }
}

{ }
{ a }
{ b }
{ a b }
{ c }
{ a c }
{ b c }
{ a b c }

Complejidad del tiempo: O(n * (2^n)) ya que el ciclo externo se ejecuta para O(2^n) y el ciclo interno se ejecuta para O(n).

Publicación relacionada:  
Encontrar todos los subconjuntos de un Conjunto en C/C++

Este artículo es una contribución de Nikhil Tekwani. Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.