Como implementar uma solução para o problema conhecido como "subset sum" usando backtracking?

Question

O problema conhecido como subset sum pode ser resumido no seguinte texto:

Dado um conjunto \(X\) com números naturais e um inteiro positivo
\(T\), deseja-se encontrar um subconjunto cuja a soma de seus elementos seja igual a \(T\).

Answer 1

Abaixo eu apresento 4 soluções diferentes usando backtracking. Todas elas se baseiam no seguinte argumento:

Existe um subconjunto que soma \(T\) se, e somente se, uma das afirmativas é verdadeira:

Existe um subconjunto de \(X\) que inclui \(x\) que a soma é \(T\)
Existe um subconjunto de \(X\) que exclui \(x\) que a soma é \(T\)

De fato, as duas primeiras soluções são baseadas nos pseudo-códigos na Lecture 3 do E-book Algorithms de Jeff Erickson. As últimas soluções usam explicitamente a representação usando árvore binária usual para resolver problemas com essas características.

1) Checa se existe um subconjunto

import numpy as np

def subset_sum_check(theSet,target):
    n=len(theSet)
    if (target==0):
        print "I found a solution"
        return True
    elif(target<0 or n==0):
        return False
    else:
        return (subset_sum_check(theSet[0:n-1],target)or(subset_sum_check(theSet[0:n-1],target-theSet[n-1])))

if __name__ == '__main__':

    theSet=np.array([8,6,7,5,3,10,9])
    target=15
    solution=[]
    print subset_sum_check(theSet,target)

2) Apresenta um subconjunto

import warnings
import numpy as np

def subset_sum(theSet,target):
    n=len(theSet)    
    if(target==0):
        return np.empty([0]) #emptySet
    if(target<0 or n==0):
        return None
    theAuxSet=subset_sum(theSet[0:n-1],target)
    if (theAuxSet is not None):
        return theAuxSet
    theAuxSet=subset_sum(theSet[0:n-1],target-theSet[n-1]) 
    if(theAuxSet is not None):
        return np.append(theAuxSet,theSet[n-1])
    return None    


if __name__ == '__main__':

    theSet=np.array([8,6,7,5,3,10,9])
    target=16
    solution=[]
    #print list(subset_sum(theSet,target))
    print subset_sum(theSet,target)

3 ) Apresenta todos os subconjuntos

a) Usando uma fila:

import numpy as np
import Queue

class Node:
    def __init__(self, level, possibleSolution):
        self.level = level # The level within the tree (depth)
        self.possibleSolution = possibleSolution    # list of items our node contains



def subset_sum(theSet,target):
    solution=[]
    n=len(theSet)
    queue = Queue.Queue()
    root = Node(-1,[])    
    queue.put(root)            
    while not queue.empty():
        u=queue.get()  
        if(u.level<n-1):
            # With the extra element
            v=Node(u.level+1,u.possibleSolution[:])
            v.possibleSolution.append(theSet[v.level])
            sumPossibleSolution=sum(v.possibleSolution)
            if(sumPossibleSolution==target):
                solution.append(v.possibleSolution)
            if(sumPossibleSolution<target):
                queue.put(v)
            # Without the extra element
            v=Node(u.level+1,u.possibleSolution[:])
            queue.put(v)
    return solution


if __name__ == '__main__':

    theSet=np.array([8,6,7,5,3,10,9])
    target=15
    solution=[]
    #print list(subset_sum(theSet,target))
    print subset_sum(theSet,target)

b) Usando uma pilha

import numpy as np

class Node:
    def __init__(self, level, possibleSolution):
        self.level = level # The level within the tree (depth)
        self.possibleSolution = possibleSolution    # list of items our node contains
    def printNode(self):
        print(self.possibleSolution,self.level, ' ,',end=' ')


def subset_sum(theSet,target):
    solution=[]
    n=len(theSet)
    root = Node(-1,[])    
    stack=[root]          
    iteration=0
    while len(stack)!=0:
        iteration=iteration+1
        print('\n',iteration)
        for i in range(len(stack)):
            stack[i].printNode()            
        u=stack.pop()
        if(u.level<n-1):
            # Without the extra element
            v=Node(u.level+1,u.possibleSolution[:])
            stack.append(v)
            # With the extra element
            v=Node(u.level+1,u.possibleSolution[:])
            v.possibleSolution.append(theSet[v.level])
            sumPossibleSolution=sum(v.possibleSolution)
            if(sumPossibleSolution==target):
                solution.append(v.possibleSolution)
                print('\n','solution',solution)
            if(sumPossibleSolution<target):
                stack.append(v)

    return solution


if __name__ == '__main__':

    theSet=np.array([8,6,7,5,3,10,9])
    target=15
    solution=[]
    print('theSolution')
    print ('\n',subset_sum(theSet,target))