Here is the problem https://www.geeksforgeeks.org/subset-sum-problem-dp-25/
I can't figure out where the code is going wrong
arr = [2, 7, 3, 8]
k = 5
n = 4
# initialisation
dp = [[0]*(k+1)]*(n+1)
for x in range(n+1):
dp[x][0] = 1
#tabulation
for i in range(1, n+1):
for j in range(1, k+1):
if arr[i-1]>j:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = dp[i-1][j] or dp[i-1][j-arr[i-1]]
for m in range(n+1):
for n in range(k+1):
print(dp[m][n], end=" ")
print()
I'm unsure what the code is doing, but the line
dp = [[0]*(k+1)]*(n+1)
is definitely wrong, as it is taking n+1
references to one list. See below:
>>> k=3
>>> n=3
>>> dp = [[0]*(k+1)]*(n+1)
>>> dp
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
>>> dp[0][0]=1
>>> dp
[[1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]