Programa Java para imprimir todos los subconjuntos únicos en una array de subconjuntos mediante la manipulación de bits

Dada una array de enteros de elementos únicos, devuelve todos los subconjuntos posibles (el conjunto potencia). El conjunto de soluciones no debe contener subconjuntos duplicados y debe devolver la solución en cualquier orden.

Ilustración:

Input: array = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Input: array = [0]
Output: [[],[0]]

Enfoque 1

Algoritmo

1. Genere todas las máscaras de bits binarias posibles de longitud n.
2. Asigne un subconjunto a cada máscara de bits
   •  1 en la i-ésima posición en la máscara de bits significa la presencia de nums[i] en el subconjunto
   • 0 significa su ausencia.
3. Lista de salida de retorno.

Implementación:

Ejemplo

// Java Program to Print all unique subsets in an array of
// subsets using bit manipulation
  
// Importing input output classes
import java.io.*;
// Importing utility classes
import java.util.*;
  
// Main class
class GFG {
  
    // Method 1
    // Helper method
    static List<List<Integer> > subsets(int[] nums)
    {
        List<List<Integer> > output = new ArrayList<>();
        int n = nums.length;
  
        for (int i = (int)Math.pow(2, n);
             i < (int)Math.pow(2, n + 1); ++i) {
  
            // Generate bitmask, from 0..00 to 1..11
            String bitmask
                = Integer.toBinaryString(i).substring(1);
  
            // Appending subset corresponding to that
            // bitmask
            List<Integer> curr = new ArrayList<>();
  
            for (int j = 0; j < n; ++j) {
                if (bitmask.charAt(j) == '1')
  
                    // Adding it to subset
                    curr.add(nums[j]);
            }
  
            // Adding the subset
            output.add(curr);
        }
        return output;
    }
  
    // Method 2
    // Main driver method
    public static void main(String[] args)
    {
        // Custom input integer array
        int arr[] = { 1, 2, 3 };
  
        // Calling method 1 in main() method
        List<List<Integer> > output = subsets(arr);
  
        // Printing all unique subsets in an array
        System.out.println(output);
    }
}

[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

Análisis de Complejidad:

• Complejidad de tiempo: – O (N x 2 ^ N) para generar todos los subconjuntos y luego copiarlos en la lista de salida.
• Complejidad espacial: – O (N x 2 ^ N) para mantener todos los subconjuntos de longitud NN ya que cada uno de los elementos NN podría estar presente o ausente.

Enfoque 2:

Ejemplo

// Java Program to Print all unique subsets in an array of
// subsets using bit manipulation
  
// Importing input output classes
import java.io.*;
// Importing utility classes
import java.util.*;
  
// Main class
class GFG {
  
    // Method 1
    static List<List<Integer> > subsets(int[] nums)
    {
  
        // Creating List class object
        // Declaring. object of integer List
        List<List<Integer> > output = new ArrayList<>();
  
        int n = nums.length;
  
        // Increase the size by using left shift (1 * 2^n)
        int size = 1 << n;
  
        for (int i = 0; i < size; i++) {
            List<Integer> curr = new ArrayList<>();
            for (int j = 0; j < n; j++) {
  
                // right shift i and j i.e. i/2^j
                if (((i >> j) & 1) == 1) {
  
                    // Add it to subset
                    curr.add(nums[j]);
                }
            }
  
            // Adding the subset
            output.add(curr);
        }
        return output;
    }
  
    // Method 2
    // Main driver method
    public static void main(String[] args)
    {
  
        // Custom input array
        int arr[] = { 1, 2, 3 };
  
        // Calling method 1 in main() method
        List<List<Integer> > output = subsets(arr);
  
        // Print all unique subsets in an array
        System.out.println(output);
    }
}

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]