CODEWITHSUNDEEP
pythonpython-3.xrecursion
sn3jd3r
sn3jd3r

Reputation: 506

Recursion in python not reaching correct result

I have the a problem of wanting to find the number of ways a subset of a list will sum to specific value. However if i run the recursive formula by hand i get a different (correct) value, than with the python code. Am i missing something, or why am i getting different results?

Assume i have a list b = [2,3,2,1,4] and a target value of T = 5. There will then be 4 subsets that sum to the target value: 

{b[0], b[1]}
{b[0], b[2], b[3]}
{b[4], b[3]}
{b[1], b[2]}

The following code gives a result of 2, but i would like it to return 4. 

b = [2,3,2,1,4]
def subset_sum(T, idx):
    if T < 0 or idx< 0:
        return 0
    if T == 0:
        return 1
    else:
        return subset_sum(T, idx-1) + subset_sum(T-b[idx], idx-1) 

if __name__ == "__main__":
    print(subset_sum(5, 4))

edit based on @TomDalton comment: I tried this and thought that it might be because of the fact that the two if statements are not check simultaneously - therefore in the case where idx = 0 and we subtract the b[0] from the value T, then in the next iteration it will return 0 because it checks if idx < 0 before it checks if T == 0. Although i am unsure of the validity of my guess

Upvotes: 2

Views: 89

Answers (3)

Merig
Merig

Reputation: 2011

Have you considered an iterative approach? itertools.combinations jumps to mind

itertools.combinations(iterable, r)

Return r length subsequences of elements from the input iterable.

Combinations are emitted in lexicographic sort order. So, if the input iterable is sorted, the combination tuples will be produced in sorted order.

With this, you could do something like:

from itertools import combinations

def count_subsets(main_list, target):
    result = 0
    for i in range(len(main_list)):
        sets = combinations(main_list, i)
        result += sum(sum(subset) == target for subset in sets)
    return result

Upvotes: 0

Prune
Prune

Reputation: 77847

Here is your code with extra instrumentation to help track the output, indenting for recursive calls.

You'll notice a critical problem with your counting: when you get the desired total and reach the end of the list, you return 0 instead of 1. This prevents you from properly accumulating solutions that achieve the correct total by using the final list element, because you recur past the end of the list before you check that you got the right total. Repair is at the bottom.

indent = ""
b = [2,3,2,1,4]

def subset_sum(total, idx):
    global indent
    print(indent + "ENTER", total, idx)
    indent += "  "

    if total < 0 or idx < 0:
        result = 0
    elif total == 0:
        result = 1
    else:
        result = subset_sum(total, idx-1) + subset_sum(total-b[idx], idx-1) 

    indent = indent[2:]
    print(indent + "LEAVE", total, idx, result)
    return result

if __name__ == "__main__":
    print(subset_sum(5, 4))

Output:

ENTER 5 4
  ENTER 5 3
    ENTER 5 2
      ENTER 5 1
        ENTER 5 0
          ENTER 5 -1
          LEAVE 5 -1 0
          ENTER 3 -1
          LEAVE 3 -1 0
        LEAVE 5 0 0
        ENTER 2 0
          ENTER 2 -1
          LEAVE 2 -1 0
          ENTER 0 -1
          LEAVE 0 -1 0
        LEAVE 2 0 0
      LEAVE 5 1 0
      ENTER 3 1
        ENTER 3 0
          ENTER 3 -1
          LEAVE 3 -1 0
          ENTER 1 -1
          LEAVE 1 -1 0
        LEAVE 3 0 0
        ENTER 0 0
        LEAVE 0 0 1
      LEAVE 3 1 1
    LEAVE 5 2 1
    ENTER 4 2
      ENTER 4 1
        ENTER 4 0
          ENTER 4 -1
          LEAVE 4 -1 0
          ENTER 2 -1
          LEAVE 2 -1 0
        LEAVE 4 0 0
        ENTER 1 0
          ENTER 1 -1
          LEAVE 1 -1 0
          ENTER -1 -1
          LEAVE -1 -1 0
        LEAVE 1 0 0
      LEAVE 4 1 0
      ENTER 2 1
        ENTER 2 0
          ENTER 2 -1
          LEAVE 2 -1 0
          ENTER 0 -1
          LEAVE 0 -1 0
        LEAVE 2 0 0
        ENTER -1 0
        LEAVE -1 0 0
      LEAVE 2 1 0
    LEAVE 4 2 0
  LEAVE 5 3 1
  ENTER 1 3
    ENTER 1 2
      ENTER 1 1
        ENTER 1 0
          ENTER 1 -1
          LEAVE 1 -1 0
          ENTER -1 -1
          LEAVE -1 -1 0
        LEAVE 1 0 0
        ENTER -2 0
        LEAVE -2 0 0
      LEAVE 1 1 0
      ENTER -1 1
      LEAVE -1 1 0
    LEAVE 1 2 0
    ENTER 0 2
    LEAVE 0 2 1
  LEAVE 1 3 1
LEAVE 5 4 2
2

REPAIR

Merely check for success before you check for running off the end of the list:

if total == 0:
    result = 1
elif total < 0 or idx < 0:
    result = 0

Upvotes: 3

trincot
trincot

Reputation: 350272

The problem is that you bail out when idx < 0, but without checking first whether maybe T == 0 (which would be a solution). You should first test T == 0:

if T == 0:
    return 1
elif T < 0 or idx< 0:
    return 0
else:
    return subset_sum(T, idx-1) + subset_sum(T-b[idx], idx-1)

Upvotes: 0

Related Questions