Encuentre todos los subconjuntos distintos de un conjunto determinado utilizando el enfoque BitMasking

Dado un conjunto de enteros positivos, encuentre todos sus subconjuntos. El conjunto no puede contener elementos duplicados, por lo que cualquier subconjunto repetido debe considerarse solo una vez en la salida.
Ejemplos: 

Input:  S = {1, 2, 2}
Output:  {}, {1}, {2}, {1, 2}, {2, 2}, {1, 2, 2}

Explanation: 
The total subsets of given set are - 
{}, {1}, {2}, {2}, {1, 2}, {1, 2}, {2, 2}, {1, 2, 2}
Here {2} and {1, 2} are repeated twice so they are considered 
only once in the output

Prerrequisito: Power Set
La idea es usar un patrón de máscara de bits para generar todas las combinaciones como se discutió en la publicación anterior . Pero la publicación anterior imprimirá subconjuntos duplicados si los elementos se repiten en el conjunto dado. Para manejar elementos duplicados, construimos una string a partir de un subconjunto dado, de modo que los subconjuntos que tengan elementos similares darán como resultado la misma string. Mantenemos una lista de tales strings únicas y finalmente decodificamos todas esas strings para imprimir sus elementos individuales.

Ilustración :

S = {1, 2, 2}

Los dígitos binarios del 0 al 7 son

0 –> 000 –> número formado sin setbits –> { }

1 –> 001 –> número formado con setbit en la posición 0 –> { 1 }

2 –> 010 –> número formado con setbit en la posición 1 –> { 2 }

3 –> 011 –> número formado con setbit en la posición 0 y 1 –> { 1 , 2 }

4 –> 100 –> número formado con setbit en la posición 2 –> { 2 }

5 –> 101 –> número formado con setbit en la posición 0 y 2 –> { 1 , 2}

6 -> 110 -> número formado con setbit en la posición 1 y 2 -> { 2 , 2}

7 –> 111 –> número formado con setbit en la posición 0, 1 y 2 –> {1, 2, 2}

Después de eliminar los duplicados, los últimos serán { }, { 1 }, { 2 }, { 1 , 2 }, { 2 , 2 }, { 1 , 2 , 2}

Nota: este método solo funcionará en una array ordenada. 
A continuación se muestra su implementación:  

// C++ program to find all subsets of given set. Any
// repeated subset is considered only once in the output
#include <bits/stdc++.h>
using namespace std;
 
// Function to find all subsets of given set. Any repeated
// subset is considered only once in the output
vector<vector<int> > findPowerSet(vector<int>& nums)
{
    int bits = nums.size();     // size of array to set bit
    unsigned int pow_set_size = pow(2, bits);     // total number of subsets = pow(2, sizeof(arr))
    sort(nums.begin(), nums.end());     // sort to avoid adding permutation of the substring
    vector<vector<int>> ans;
    vector<string> list;     // to store subset as a list to avoid adding exact duplicates
 
     
    // counter 000..0 to 111..1
    for (int counter = 0; counter < pow_set_size; counter++) {
        vector<int> subset;
        string temp = "";
     
        // check for the current bit in the counter
        for (int j = 0; j < bits; j++) {
            if (counter & (1 << j)) {
                subset.push_back(nums[j]);
                // add special character to separate integers
                temp += to_string(nums[j]) + '$';
            }
        }
     
        if (find(list.begin(), list.end(), temp) == list.end()) {
            ans.push_back(subset);
            list.push_back(temp);
        }
    }
 
    return ans;
}
 
// Driver code
int main()
{
    vector<int> arr{ 10,12,12 };
 
    vector<vector<int> > power_set = findPowerSet(arr);
     
    for(int i=0;i<power_set.size();i++)
    {
        for(int j=0;j<power_set[i].size();j++)
        cout<<power_set[i][j]<<" ";
        cout<<endl;
    }
 
    return 0;
}
// this code is contributed by prophet1999

// Java program to find all subsets of given set. Any
// repeated subset is considered only once in the output
import java .io.*;
import java.util.*;
  
public class GFG {
      
    // Function to find all subsets of given set. Any repeated
    // subset is considered only once in the output
    static void printPowerSet(int []set, int set_size)
    {
         
        ArrayList<String> subset = new ArrayList<String>();
          
        /*set_size of power set of a set
        with set_size n is (2**n -1)*/
        long pow_set_size =
            (long)Math.pow(2, set_size);
        int counter, j;
      
        /*Run from counter 000..0 to
        111..1*/
        for(counter = 0; counter <
                pow_set_size; counter++)
        {
            String temp = "";
            for(j = 0; j < set_size; j++)
            {
                /* Check if jth bit in the
                counter is set If set then
                print jth element from set */
                if((counter & (1 << j)) > 0)
                    temp += (Integer.toString(set[j])+'$');
            }
             
            if(!subset.contains(temp) && temp.length()>0)
            {
                subset.add(temp);
            }
        }
         
        for(String s:subset) {
            s = s.replace('$',' ');
            System.out.println(s);
        }
    }
      
    // Driver program to test printPowerSet
    public static void main (String[] args)
    {
        int []set = {10, 12, 12};
        printPowerSet(set, 3);
    }
}
  
// This code is contributed by Aditya Patil.

# Python3 program to find all subsets of
# given set. Any repeated subset is
# considered only once in the output
def printPowerSet(arr, n):
     
    # Function to find all subsets of given set.
    # Any repeated subset is considered only
    # once in the output
    _list = []
 
    # Run counter i from 000..0 to 111..1
    for i in range(2**n):
        subset = ""
 
        # consider each element in the set
        for j in range(n):
 
            # Check if jth bit in the i is set.
            # If the bit is set, we consider
            # jth element from set
            if (i & (1 << j)) != 0:
                subset += str(arr[j]) + "|"
 
        # if subset is encountered for the first time
        # If we use set<string>, we can directly insert
        if subset not in _list and len(subset) > 0:
            _list.append(subset)
 
    # consider every subset
    for subset in _list:
 
        # split the subset and print its elements
        arr = subset.split('|')
        for string in arr:
            print(string, end = " ")
        print()
 
# Driver Code
if __name__ == '__main__':
    arr = [10, 12, 12]
    n = len(arr)
    printPowerSet(arr, n)
 
# This code is contributed by vibhu4agarwal

<script>
    // JavaScript program to find all subsets of given set. Any
    // repeated subset is considered only once in the output
 
    // Function to find all subsets of given set. Any repeated
    // subset is considered only once in the output
    const findPowerSet = (nums) => {
        let bits = nums.length;     // size of array to set bit
        let pow_set_size = Math.pow(2, bits);     // total number of subsets = pow(2, sizeof(arr))
        nums.sort();     // sort to avoid adding permutation of the substring
        let ans = [];
        let list = [];     // to store subset as a list to avoid adding exact duplicates
 
 
        // counter 000..0 to 111..1
        for (let counter = 0; counter < pow_set_size; counter++) {
            let subset = [];
            let temp = "";
 
            // check for the current bit in the counter
            for (let j = 0; j < bits; j++) {
                if (counter & (1 << j)) {
                    subset.push(nums[j]);
                    // add special character to separate integers
                    temp += nums[j].toString() + '$';
                }
            }
 
            if (list.indexOf(temp) == -1) {
                ans.push(subset);
                list.push(temp);
            }
        }
 
        return ans;
    }
 
    // Driver code
 
    let arr = [10, 12, 12];
 
    let power_set = findPowerSet(arr);
 
    for (let i = 0; i < power_set.length; i++) {
        for (let j = 0; j < power_set[i].length; j++)
            document.write(`${power_set[i][j]} `);
        document.write("<br/>");
    }
 
// This code is contributed by rakeshsahni
 
</script>

10 
12 
10 12 
12 12 
10 12 12 

Complejidad de tiempo: O (N*2 ^N )

Espacio Auxiliar: O(N*N)

Análisis:

Si    es el número total de pasos en el código, entonces el ciclo para generar todas las combinaciones binarias se ejecuta hasta   y luego el ciclo interno se ejecuta hasta log(i).

Por eso, 

Elevando a la potencia de dos en ambos lados obtenemos

Usando log en ambos lados y aplicando la aproximación de Sterling obtenemos,

Por lo tanto, la complejidad del tiempo es 

Otro enfoque :

Usar el rastreo hacia atrás para encontrar todos los subconjuntos posibles junto con una lista global que nos ayuda a rastrear subconjuntos únicos.

# Python3 program to find all subsets of
# given set. Any repeated subset is
# considered only once in the output
 
 
def PowerSet(a, s, index):
    # Base condition if len(a) = index, return
    if index == len(a):
        return
 
    # traversing loop from index to length of array
    for i in range(index, len(a)):
        # addng new element to the list
        # creating new subset
        s.append(str(a[i]))
 
        # checking if subset exists in global list
        # if not add it to the global list
        # print the subset
        if ''.join(s) not in h:
            h.append(''.join(s))
            print(*s)
        # call recursion again for next index
        PowerSet(a, s, i+1)
 
        # remove the element from the list once
        # recursive call is over
        s.pop()
 
 
# Driver Code
if __name__ == '__main__':
    arr = [10, 12, 12]
    n = len(arr)
    h = []
    PowerSet(arr, [], 0)
# This code is contributed by Anvesh Govind Saxena

10
10 12
10 12 12
12
12 12

Complejidad de tiempo: O(N*2N)

Espacio Auxiliar: O(N*N)

Consulte el siguiente artículo para resolver el problema utilizando el enfoque de retroceso.

https://www.geeksforgeeks.org/backtracking-to-find-all-subsets/

Este artículo es una contribución de Aditya Goel . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.GeeksforGeeks.org o envíe su artículo por correo a contribuya@GeeksforGeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.