I want to point out that this is actually a pretty bad way to solve subset sum.
First generalize the problem to trying to sum to a specified target rather than zero. We can do this WLOG by just adding the absolute minimum value to every item.
The standard DP approach is much more efficient and isn't based on just iterating through combos hoping for a hit.
Let
This gives the recursive formulation:
If you try this with your program (you will have to alter it to sum to a target instead of zero which is simple), you will find yours takes quite a lot longer. More than this though, if hypothetically there was no such solution, the DP version would still take the same time; whereas yours might approach the heat death of the universe.
Of course the DP version is still not polynomial in the input size of the problem (it is what we call psuedo-polynomial).
First generalize the problem to trying to sum to a specified target rather than zero. We can do this WLOG by just adding the absolute minimum value to every item.
The standard DP approach is much more efficient and isn't based on just iterating through combos hoping for a hit.
Let
T[i,j] be a boolean representing whether the first i items of our sequence can sum to j.This gives the recursive formulation:
if j >= ith value:
T[i,j] = T[i-1, j-value] or T[i-1, j]
else:
T[i,j] = T[i-1, j]Fill in the table row by row:import numpy as np
def subset_sum(sequence, target):
T = np.zeros((len(sequence)+1, target+1), dtype=int)
T[:,0] = 1
for i,num in enumerate(sequence, start=1):
for j in range(1, target+1):
if j >= num:
T[i,j] = T[i-1, j-num] or T[i-1, j]
else:
T[i,j] = T[i-1, j]
return TWe can then reconstruct the set from this table (could be cleaned up a bit):def subset_sum_solution(sequence, target):
T = subset_sum(sequence, target)
n = len(sequence)
solution = []
if T[n,target]:
while n > 0 and target > 0:
if not T[n-1, target]:
solution.append(sequence[n-1])
target -= sequence[n-1]
n -= 1
return solutionNow lets create a big enough problem so we can see the difference in efficiency:If you try this with your program (you will have to alter it to sum to a target instead of zero which is simple), you will find yours takes quite a lot longer. More than this though, if hypothetically there was no such solution, the DP version would still take the same time; whereas yours might approach the heat death of the universe.
Of course the DP version is still not polynomial in the input size of the problem (it is what we call psuedo-polynomial).