Finds all of the subsets of set S whose elements add up to V

SubsetSum.py

###############################################################################
#   Subset Sum Problem
#   Find all subsets s of S that sum to value V
#
#                                   include value   exclude value
#   Recursive Equation: SS(S, V) = SS(S-1, V - s_v) + SS(S-1, V)
#
###############################################################################

#Retrieves actual subsets in solution. Based on (https://stackoverflow.com/questions/42417352/subset-sum-recover-solution)
#Starts on top element of final column traversing down. When a number changes that means it is the max element in that
#subset. Traverse backwards using a greedy approach subtracting from the total if the current element is smaller
'''
Iterate through the results of the target column in ascending order. When the result increments, you have identified
another subset and have found the largest value in that subset. To find the remaining values in the subset,
"make change" the way a store clerk would. In other words, walk back down the set values, subtracting from the remaining
total as you can. - (https://stackoverflow.com/questions/42417352/subset-sum-recover-solution)
'''
#Doesn't work if the max element of two different subsets is the same. In that case it will only create the subset
#with the largest elements
def SubSets(matrix, num_set, num):
    #Initialize variables
    height = len(matrix)
    width = num
    subset_list = []
    s = matrix[0][num-1] #Keeps track of number until a change occurs

    for i in range(1, height):
        current = matrix[i][width]
        if current > s:
            s = current #keeps track of changing value
            cnt = i -1 #backwards counter, -1 to exclude current value already appended to list
            templist = []   #to store current subset
            templist.append(num_set[i-1]) #Adds current element to subset
            total = num - num_set[i-1] #Initial total will be sum - max element
            
            while cnt > 0:  #Loop backwards to find remaining elements
                if total >= num_set[cnt-1]: #Takes current element if it is less than total
                    templist.append(num_set[cnt-1])
                    total = total - num_set[cnt-1]
                cnt = cnt - 1

            templist.sort()
            subset_list.append(templist) #Add subset to solution set
                
    return subset_list
            
#Retrieves all elements in subsets of solutions w/o grouping them
def recoverSet(matrix, num_set):
    height = len(matrix) - 1
    width = len(matrix[0]) - 1
    subsets = []

    while height > 0:
        current = matrix[height][width]
        top = matrix[height-1][width]

        if current > top:
            subsets.append(num_set[height-1])
        if top == 0:
            width = width - num_set[height-1]
        height -= 1

    return subsets

#Dynamic Programming method
def setsum(num_set, num_sum):
    #Initialize DP matrix with base cases set to 1
    matrix = [[0 for i in range(0, num_sum+1)] for j in range(0, len(num_set)+1)]
    for i in range(len(num_set)+1): matrix[i][0] = 1
   
    for i in range(1, len(num_set)+1): #Iterate through set elements
        for j in range(1, num_sum+1):   #Iterate through sum
            if num_set[i-1] > j:    #When current element is greater than sum
                matrix[i][j] = matrix[i-1][j]
            else:
                matrix[i][j] = matrix[i-1][j] + matrix[i-1][j-num_set[i-1]]

    #Retrieve elements of subsets    
    #subsets = recoverSet(matrix, num_set)
    subsets = SubSets(matrix, num_set, num_sum)

    return subsets

#Recursive method
def setsumrec(num_set, num_sum):
    #Base cases: 1 if sum is 0, 0 if sum > 0 but empty set
    if len(num_set) == 0 and num_sum > 0:
        return 0
    elif num_sum == 0:
        return 1
    
    final = 0 #Store final answer
    subset = []
    for i in range(len(num_set)):
        #With current value
        dummy1 = setsumrec(num_set[0:i]+num_set[i+1:], num_sum-num_set[i])
        #w/o current value
        dummy2 = setsumrec(num_set[0:i]+num_set[i+1:], num_sum)
        final = dummy1 + dummy2
        #Code below would append elements in subset to list but difficult to retrieve
        if dummy1 > 0 and num_set[i] not in subset:
            subset.append(num_set[i])

    return final
    
#Pring matrix in more readable format
def printMat(m):
    for i in m:
        print(i)
    print(" ")

a = [2, 3, 5, 6, 8, 10]
s = 10
    
ans = setsumrec(a,s)
x = setsum(a,s)
print(ans, " subset(s) which are: ", x)  
''' 
a = [2, 3, 5, 6, 8, 10]
s = 10
Solutions:  5 2 3
            8 2
            10
'''


b = [1, 2, 3, 7]
s = 6

ans = setsumrec(b,s)
x = setsum(b,s)
print(ans, " subset(s) which are ", x)
'''
b = [1, 2, 3, 7]
s = 10
Solutions:  3 2 1
'''




c = [1, 2, 3, 4, 5]
s = 10
        
ans = setsumrec(c,s)
x = setsum(c,s)
print(ans, " subset(s) which are ", x)
'''
c = [1, 2, 3, 4, 5]
s = 10
Solutions:  4 3 2 1
            5 3 2
            5 4 1
'''