Number of subsets with a given sum . Recursion not tracing few branches of the tree

Question

I have written this code in python and it is not yielding the right answer for the input wt[]=[2,3,5,6,8,10] in this order . It is giving right answer for few other combinations like wt[]=[3,2,6,10,8,5].I I have also tried tracing the recursive tree to debug accordingly but still cannot figure out why the code is not tracing some branches of the tree. Kindly please help me figure out the problem. Thank you!

n=6      #int(input())
m=10     #int(input())
wt=[2,3,5,6,8,10]
dp_table=[[-1 for i in range(n+1)]for j in range (m+1)]
total=[0]
def SS(m,n):
    a=0
    b=0
    if m==0:
        print(n-1)
        total[0]=total[0]+1 
        return 0;
    if n==0:
        return 0;
    else:
        if wt[n-1]>m:
            return (SS(m,n-1));
        else:
            if dp_table[m-wt[n-1]][n-1]==-1:
                a=SS(m-wt[n-1],n-1) + wt[n-1]
            if dp_table[m][n-1]==-1:
                b=SS(m,n-1)
            dp_table[m][n]=max(a,b)
               
        return dp_table[m][n];
if m==0 or n==0:
    print("Not Possible!")          
if SS(m,n)==m:
    print("Possible and the no of subsets with equal sum are: ",total[0])
else:
    print("False")

Answer 1

You're storing results in dp_table but never using them (giving incorrect results). If the dp_table value of an entry isn't -1, you're ignoring the result (and assuming it's always 0).

Often it's better to do the cache-checks at the top of the function (or better yet, use functools.cache).

If you really want to keep the code structured as it is now, this will fix the issue:

def SS(m, n):
    a = dp_table[m - wt[n - 1]][n - 1]
    b = dp_table[m][n - 1]
    if m == 0:
        total[0] += 1
        return 0
    if n == 0:
        return 0
    else:
        if wt[n - 1] > m:
            dp_table[m][n] = b if b != -1 else SS(m, n - 1)
        else:
            if a == -1:
                a = SS(m - wt[n - 1], n - 1)
            a += wt[n - 1]
            if b == -1:
                b = SS(m, n - 1)
            dp_table[m][n] = max(a, b)

        return dp_table[m][n]

If you want to do the caching yourself, you can put cache checks at the top (a better approach), rather than putting a check (and an if-else statement) before every recursive call, like this:

def SS2(m, n):
    if dp_table[m][n] != -1:
        return dp_table[m][n]
    if m == 0:
        total[0] += 1
        dp_table[m][n] = 0
    elif n == 0:
        dp_table[m][n] = 0
    else:
        if wt[n - 1] > m:
            dp_table[m][n] = SS(m, n - 1)
        else:
            dp_table[m][n] = max(SS(m - wt[n - 1], n - 1) + wt[n - 1], SS(m, n - 1))

    return dp_table[m][n]

But the most 'Pythonic' and least work alternative is to use the decorators built into the standard library. You can limit the total memory usage, and it might even be faster if your manual DP-table happens to have cache-unfriendly access patterns.

import functools

@functools.cache
def SS3(m, n):
    if m == 0:
        total[0] += 1
        return 0
    elif n == 0:
        return 0
    else:
        if wt[n - 1] > m:
            return SS(m, n - 1)
        else:
            return max(SS(m - wt[n - 1], n - 1) + wt[n - 1], SS(m, n - 1))