python 3.x - Dynamic programming problem find number of subsets that add up to target

Question

The problem is to find the number of subsets that add up to a target, for example, if the target is 16 and the array is [2, 4, 6, 10], it should return 2, because 2 + 4 + 10 = 16 and 10 + 6 = 16. I tried to make the recursive solution. I need help to figure out where is the mistake in my code. This is my code:

def num_sum(target, arr, ans=0 ):
if target == 0:
    return 1

elif target < 0:
    return 0

for i in arr:
    arr.remove(i)
    num = num_sum(target - i, arr, ans)
    ans += num
return ans

print(num_sum(16, [2, 4, 6, 10]))

Thanks in advance.

question from:https://stackoverflow.com/questions/65947195/dynamic-programming-problem-find-number-of-subsets-that-add-up-to-target

Answer 1

You are trying to use backtracking to calculate the subsets that add up to a target. However, in your code, you keep removing the item from the arr, and it was not added back for backtracking. That's why it prints only 4 times, as the arr size is getting smaller during the recursion.

But in this case, your arr should not be changed, as it can be in different subsets to make up to the target, for example the number 10 in your example. So I would use an index to note the current position ,and then exam the remaining to see if it adds up to a target.

Here is my sample code for your reference. I used an int array as a mutable result holder to hold the result for each recursion.

def num_sum(current_index, target, arr, ans):
    if target == 0:
        ans[0]+=1;
        return

    elif target < 0:
        return

    for i in range(current_index, len(arr)):
        num_sum(i+1, target - arr[i], arr, ans)
        

ans = [0]    
num_sum(0, 16, [2, 4, 6, 10, 8], ans)
print(ans[0])