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.
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.
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.
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.
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]))
