Subconjunto suma recursivamente en Python

Question

Estaré encantado de obtener ayuda.

Tengo el siguiente problema:

estoy dado una lista de números de seq y un número de destino y necesito escribir 2 cosas:

1. Una solución recursiva que devuelve True si hay es una suma de una subsecuencia que es igual al número objetivo y False en caso contrario. ejemplo:

   subset_sum([-1,1,5,4],0) # True 
   subset_sum([-1,1,5,4],-3) # False 
   

2. En segundo lugar, tengo que escribir una solución con lo que escribí en la solución anterior pero ahora con memoization que utiliza un diccionario en el que las claves son tuplas: (len(seq),target)

para el número 1 esto es lo que tengo que hasta el momento:

def subset_sum(seq, target): 
    if target == 0: 
     return True 
    if seq[0] == target: 
     return True 
    if len(seq) > 1: 
     return subset_sum(seq[1:],target-seq[0]) or subset_sum(seq[1:],target) 
    return False 

No estoy seguro lo hice bien, así que si pudiera obtener algo, lo agradeceré.

Para el número 2:

def subset_sum_mem(seq, target, mem=None): 
    if not mem: 
     mem = {} 
    key=(len(seq),target) 
    if key not in mem: 
     if target == 0 or seq[0]==target: 
      mem[key] = True 
     if len(seq)>1: 
      mem[key] = subset_sum_mem(seq[1:],target-seq[0],mem) or subset_sum_mem(seq[1:],target,mem) 
     mem[key] = False 

    return mem[key] 

no puedo conseguir el memoization darme la respuesta correcta por lo que me alegraría por alguna orientación aquí.

¡Gracias a todos los que quieran ayudar!

Answer 1

tengo este código modificado:

def subset_sum(seq, target): 
    left, right = seq[0], seq[1:] 
    return target in (0, left) or \ 
     (bool(right) and (subset_sum(right, target - left) or subset_sum(right, target))) 

def subset_sum_mem(seq, target, mem=None): 
    mem = mem or {} 
    key = (len(seq), target) 
    if key not in mem: 
     left, right = seq[0], seq[1:] 
     mem[key] = target in (0, left) or \ 
      (bool(right) and (subset_sum_mem(right, target - left, mem) or subset_sum_mem(right, target, mem))) 
    return mem[key] 

¿Puede dar algunos casos de prueba, esto no trabaja?

Answer 2

Ésta es la forma en que me gustaría escribir la subset_sum:

def subset_sum(seq, target): 
    if target == 0: 
     return True 

    for i in range(len(seq)): 
     if subset_sum(seq[:i] + seq[i+1:], target - seq[i]): 
      return True 
    return False 

Se trabajó en un par de ejemplos:

>>> subset_sum([-1,1,5,4], 0)) 
True 
>>> subset_sum([-1,1,5,4], 10) 
True 
>>> subset_sum([-1,1,5,4], 4) 
True 
>>> subset_sum([-1,1,5,4], -3) 
False 
>>> subset_sum([-1,1,5,4], -4) 
False 

Para ser honesto, no sabría cómo memoize ella.

Edición anterior: Eliminé la solución con any() porque después de algunas pruebas descubrí que era más lento.

Actualización: Sólo por curiosidad se podría también utilizar itertools.combinations:

from itertools import combinations 

def com_subset_sum(seq, target): 
    if target == 0 or target in seq: 
     return True 

    for r in range(2, len(seq)): 
     for subset in combinations(seq, r): 
      if sum(subset) == target: 
       return True 
    return False 

Esto se puede hacer mejor que el enfoque de programación dinámica en algunos casos, pero en otros se colgará (que es de todos modos mejor que la recursiva enfoque).

Answer 3

Sólo como referencia, he aquí una solución utilizando programación dinámica:

def positive_negative_sums(seq): 
    P, N = 0, 0 
    for e in seq: 
     if e >= 0: 
      P += e 
     else: 
      N += e 
    return P, N 

def subset_sum(seq, s=0): 
    P, N = positive_negative_sums(seq) 
    if not seq or s < N or s > P: 
     return False 
    n, m = len(seq), P - N + 1 
    table = [[False] * m for x in xrange(n)] 
    table[0][seq[0]] = True 
    for i in xrange(1, n): 
     for j in xrange(N, P+1): 
      table[i][j] = seq[i] == j or table[i-1][j] or table[i-1][j-seq[i]] 
    return table[n-1][s]