bug in subset sum algorithm

[usercat123]

Given an array of integers and a value k, return True if there exists a subset of elements of the array that sums up to k.
This is my algorithm. Initially, the line that I commented was included and the result was that the algorithm outputted True when the answer should have been False. Without the line it seems to work fine. I do not understand why there is a difference in output, can somebody explain?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

def solve(arr,items,sum,dp):     if sum - arr[items] >= 0:         dp[items][sum] = max(dp[items-1][sum],dp[items-1][sum-arr[items]])     else:         dp[items][sum] = dp[items-1][sum]   def driver(arr,k):     dp = [[False for j in range(k+1)] for i in range(len(arr))]     for i in range(len(arr)):         dp[i][0] = True         #why does this not work if the line below is executed?         #dp[i][arr[i]] = True     for i in range(len(arr)):         for j in range(k+1):             solve(arr,i,j,dp)     return dp[len(arr)-1][k]

[deanhystad]

Line 12 blows up if there are any values in arr > k. But other than that it appears to work for me. Can you provide a test case where commenting out line 12 makes a difference?

You can initialize your 2D list like this:

1	dp = [[False]*(k+1) for _ in range(len(arr))]

[value]*count works fine if value is not mutable.

[usercat123]

Yes, I was aware that there will be an exception if arr[i] > k for some i.

1 2	arr = [2,4,5,6] print(driver(arr,19))

I get True with line 12 executed and False if its not executed.

[deanhystad]

The reason for that is because you are using dp[-1] when you process dp[0].

When you run your code using arr= [2,4,5,6] and sum = 19 (do not use names of built-in functions as variable names), you incorrectly set dp[0][6] = True because dp[-1] is using relative indexing and returning dp[3]. This is easy to see if you print out dp.

1 2 3 4 5 6 7 8 9 10 11 12 13

def driver(arr,k):     dp = [[False for j in range(k+1)] for i in range(len(arr))]     for i in range(len(arr)):         dp[i][0] = dp[i][arr[i]] = True     for i in range(len(arr)):         for j in range(k+1):             solve(arr,i,j,dp)       for value, partial_sums in zip(arr, dp):         print(value, partial_sums)     return dp[len(arr)-1][k]   driver([2, 4, 5, 6], 19)

Output:
2 [True, False, True, False, False, False, True, False, True, False, False, False, False, False, False, False, False, False, False, False]
4 [True, False, True, False, True, False, True, False, True, False, True, False, True, False, False, False, False, False, False, False]
5 [True, False, True, False, True, True, True, True, True, True, True, True, True, True, False, True, False, True, False, False]
6 [True, False, True, False, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True]

dp[0] should be [True, False, True, False...False] Instead you can see dp[6] and dp[8] are also True, in effect adding an extra 6 to arr. To fix the problem you need to process dp[0] differently than dp[1]...dp[N].

The range for the inner loop is also wrong. This doesn't result in any errors, but you are wasting time updating dp[x][0] which is never used.

Using max(a, b) when a and b are booleans is strange. You should use or.

Your variable names are not descriptive. This makes your code difficult to read.

There is no recursion, so no need for any kind of "driver" function.

This is how I would write the code.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

def found_subset_totalling(values, total):     """Return True if some combination of values adds up to total"""     # Is total contained in the values list?     if total == 0 or total in values:         return True         # Remove any values outside the range 0..total     values = [v for v in values if 0 < v < total]          # Totals is a table used to keep track of partial sums.     # If values = [1, 3] and total = 5,     #   table[0] = [False, True, False, False, False, False] because partial sums of 1 are 1     #   table[1] = [False, True, False, True, True, False] because partial sums of 1 and 3 are are 1, 3, 4     totals = [[False]*(total+1) for _ in values]     for valuex, value in enumerate(values):         if valuex > 0:             # Sum value with previous partial sums.  New partial sums all >= value             for t in range(1, value):                totals[valuex][t] = totals[valuex-1][t]             for t in range(value, total+1):                totals[valuex][t] = totals[valuex-1][t] or totals[valuex-1][t-value]         totals[valuex][value] = True     return totals[valuex][total]   print(found_subset_totalling([9, 3, 88, -7, 7], 19))

Looking at that I realize only totals[i] and totals[i-1] are used and that most of totals[i] is a copy of totals[i-1]. Then I noticed if you process totals starting from the end you only need one list.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

def found_subset_totalling(values, total):     """Return True if some combination of values adds up to total"""     # Is total contained in the values list?     if total == 0 or total in values:         return True         # Remove any values outside the range 0..total     values = [v for v in values if 0 < v < total]          partial_sums = [False]*(total+1)     for value in values:         for t in range(total, value, -1):             partial_sums[t] = partial_sums[t] or partial_sums[t-value]         partial_sums[value] = True     return partial_sums[total]   print(found_subset_totalling([2, 4, 5, 6], 19))

That works, but all you get is True or False. Not very useful. I would solve the problem by computing a set of partial sums.

1 2 3 4 5 6 7 8 9

def partial_sums(values):     """Return set of sums that can be computed using combinations of values"""     items = {0}     for value in values:         for partial in list(items):             items.add(partial + value)     return items   print(19 in partial_sums([9, 3, 88, -7, 7]))