Programa de Python para obtener todos los subconjuntos que tienen suma x

Nos dan una lista de n números y un número x, la tarea es escribir un programa en python para encontrar todos los subconjuntos posibles de la lista tal que su suma sea x.

Ejemplos:

Entrada: array = [2, 4, 5, 9], x = 15

Salida: [2, 4, 9]

15 se pueden obtener sumando 2, 4 y 9 de la lista dada.

Entrada: array = [10, 20, 25, 50, 70, 90], x = 80

Salida: [10, 70]

         [10, 20, 50]

80 se puede obtener sumando 10 y 70 o sumando 10, 20 y 50 de la lista dada.

Enfoque #1:

Es un enfoque de fuerza bruta. Encuentre todas las sumas de subconjuntos posibles de la lista dada y verifique si la suma es igual a x. La complejidad del tiempo usando este enfoque sería O(2^n) que es bastante grande.

# Python code with time complexity
# O(2^n)to print all subsets whose
# sum is equal to a given value
from itertools import combinations
  
  
def subsetSum(n, arr, x):
    
    # Iterating through all possible
    # subsets of arr from lengths 0 to n:
    for i in range(n+1):
        for subset in combinations(arr, i):
              
            # printing the subset if its sum is x:
            if sum(subset) == x:
                print(list(subset))
  
  
# Driver Code:
n = 6
arr = [10, 20, 25, 50, 70, 90]
x = 80
subsetSum(n, arr, x)

Producción:

[10, 70]
[10, 20, 50]

Enfoque #2:

Meet in the middle es una técnica que divide el espacio de búsqueda en dos partes del mismo tamaño, realiza una búsqueda separada en ambas partes y luego combina los resultados de la búsqueda. Usando esta técnica, las dos búsquedas pueden requerir menos tiempo que una búsqueda grande y cambiar la complejidad del tiempo de O(2^n) a O(2^(n/2)). 

# Efficient Python code to
# print all subsets whose sum
# is equal to a given value
from itertools import combinations
  
  
def subsetSum(li, comb, sums):
    # Iterating through all subsets of
    # list li from length 0 to length of li:
    for i in range(len(li)+1):
        for subset in combinations(li, i):
              
            # Storing all the subsets in list comb:
            comb.append(list(subset))
              
            # Storing the subset sums in list sums:
            sums.append(sum(subset))
  
  
def calcSubsets(n, arr, x):
    
    # Dividing the list arr into two lists
    # arr1 and arr2 of about equal sizes
    # by slicing list arr about index n//2:
    arr1, arr2 = arr[:n//2], arr[n//2:]
      
    # Creating empty lists comb1 and sums1
    # to run the subsetSum function and
    # store subsets of arr1 in comb1
    # and the subset sums in sums1:
    comb1, sums1 = [], []
    subsetSum(arr1, comb1, sums1)
      
    # Creating empty lists comb2 and sums2
    # to run the subsetSum function and
    # store subsets of arr2 in comb2
    # and the subset sums in sums2:
    comb2, sums2 = [], []
    subsetSum(arr2, comb2, sums2)
      
    # Iterating i through the indices of sums1:
    for i in range(len(sums1)):
          
        # Iterating j through the indices of sums2:
        for j in range(len(sums2)):
              
            # If two elements (one from sums1
            # and one from sums2) add up to x,
            # the combined list of elements from
            # corresponding subsets at index i in comb1
            # and j in comb2 gives us the required answer:
            if sums1[i] + sums2[j] == x:
                print(comb1[i] + comb2[j])
  
  
# Driver Code:
n = 6
arr = [10, 20, 25, 50, 70, 90]
x = 80
calcSubsets(n, arr, x)

Producción:

[10, 70]
[10, 20, 50]