the code is very simple i am taking or not taking an element from A array and using left i am keeping track left sum it is interview bit problem
Subset Sum Problem!
class Solution:
def solve(self, A, B):
dp = []
for _ in range(len(A)+1):
dp.append([-1]*(B+1))
def rec(index,left):
if left < 0 or index==len(A):
return False
elif left == 0:
return True
if dp[index][left] != -1:
return dp[index][left]
dp[index][left] = rec(index+1,left) or rec(index+1,left-A[index])
return dp[index][left]
if rec(0,B):
return 1
else:
return 0
why this code is giving wrong output if i am getting left < 0 and index == n then i am returning False but this below one is correct
class Solution:
def solve(self, A, B):
dp = [[-1 for _ in range(B+1)] for _ in range(len(A)+1)]
def rec(index, left):
if index == len(A):
if left == 0:
return True
else:
return False
if dp[index][left] != -1:
return dp[index][left]
# Excluding the current element
exclude = rec(index + 1, left)
# Including the current element
include = False
if left - A[index] >= 0:
include = rec(index + 1, left - A[index])
dp[index][left] = exclude or include
return dp[index][left]
return int(rec(0, B))
One issue is that your rec function returns False when index==len(A). However, it doesn't then take into account that left might be 0, which would still indicate success.
So swap the order of the tests, first testing whether left == 0:
if left == 0:
return True
elif left < 0 or index==len(A):
return False
It was not mentioned in the question, but apparently it is assumed that the input values are non-negative, as the code that you call correct does not work well for inputs with negative values, like for instance solve([-4, 14], 10) produces an error with that code.
With that assumption in mind you did well to bail out immediately with left < 0, which the other code version doesn't do, losing time with further recursive calls that lead to nothing.