Subset Sum in python using DP

Question

I'm following this link to write a DP solution for Subset problem.

def subsetSum(input, target):
    row, col = len(input)+1, target+1
    db = [[False] * col] * row
    for i in range(row):
        db[i][0] = True

    for i in range(1, row):
        for j in range(1, col):
            db[i][j]=db[i-1][j]
            if db[i][j]==False and j>=input[i-1]:
                db[i][j] = db[i-1][j-input[i-1]]

    return db[i][j]

target = 5
input = [1,3,9,2]
subsetSum(input, target)

Interestingly after every iteration of "j", db[i-1] (the previous row where we are referring to the values) is also getting updated. I'm really lost whats happening here. Please suggest.

Please find this link for the printed statements.

Answer 1

The issue is in this line db = [[False] * col] * row. When you use the * operator, a copy of the original list is made that refers to the original list.

Consider the following example:

l = [[1]*5]*3
print(l) # prints [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]
l[0][0] = 0
print(l) # prints [[0, 1, 1, 1, 1], [0, 1, 1, 1, 1], [0, 1, 1, 1, 1]]

Each inner list refers to the same object. Thus, when the first element of the first list is changed, all lists appear to change.

To remedy this, you can use a list comprehension:

l = [[1]*5 for _ in range(3)]
print(l) # prints [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]
l[0][0] = 0
print(l) # prints [[0, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]

Specifically, you can replace your assignment to db with the following:

db = [[False]*col for _ in range(row)].