pythondynamic-programmingsubset-sum

Can someone spot the bug in this program?


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()

Solution

  • 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]]