Runtime Error - can only concatenate list (not "int") to list

Question

I've been doing 0-1 Knapsack problem using recursion+memoization.

My Code:

def knapSack(W, wt, val, n):
    '''
    :param W: capacity of knapsack 
    :param wt: list containing weights
    :param val: list containing corresponding values
    :param n: size of lists
    :return: Integer
    '''
    t = [[-1 for x in range(W + 1)] for j in range(n + 1)]
    if n == 0 or W == 0: 
        return 0
    if t[n][W] != -1: 
        return t[n][W] 
    elif wt[n-1] <= W: 
        t[n][W] = max(val[n-1]+knapSack(W-wt[n-1],wt,val,n-1),knapSack(W,wt,val,n-1))
        return t[n][W] 
    elif wt[n-1] > W: 
        t[n][W] = knapSack(wt, val, W, n-1) 
        return t[n][W]

Why am I getting a runtime error.

Runtime ErrorTraceback (most recent call last):
  File "/home/e8c2fc67721232cbee976a6adfc2c990.py", line 41, in <module>
    print(knapSack(W,wt,val,n))
  File "/home/e8c2fc67721232cbee976a6adfc2c990.py", line 12, in knapSack
    t[n][W] = knapSack(wt, val, W, n-1) 
  File "/home/e8c2fc67721232cbee976a6adfc2c990.py", line 5, in knapSack
    t = [[-1 for x in range(W + 1)] for j in range(n + 1)]
  File "/home/e8c2fc67721232cbee976a6adfc2c990.py", line 5, in <listcomp>
    t = [[-1 for x in range(W + 1)] for j in range(n + 1)]
TypeError: can only concatenate list (not "int") to list

This is the runtime error deatils I'm getting.

Answer 1

I suspect that there is a mismatch between the parameter-order of your function definition, and the argument-order in which the args are actually being passed to one of the many invocations.

Note that, in the traceback:

At line 41 it shows the arg-order as print(knapSack(W,wt,val,n))

At line line 12 it shows a different arg-order knapSack(wt, val, W, n-1)

For the condition elif wt[n-1] > W:, your recursive invocation of knapSack() is definitely passing the args in the wrong order.