Python understanding recursive program

Question

I am trying to understand the following program to find a number of the subset which forms a given sum from a given list.

def count_sets(arr, total):
    return rec(arr, total, len(arr)-1)


def rec(arr, total, i):
    print(arr, total, i)
    if total == 0:
        return 1
    if i < 0:
        return 0

    if arr[i] > total:
        return rec(arr, total, i-1)

    else:
        return rec(arr, total-arr[i], i-1) + rec(arr, total, i-1)

arr = [2,10,6,4]
print(count_sets(arr, 16))

the program works without any error, however, I am not able to find how it works.

recnac · Accepted Answer · 2019-04-12 13:45:03Z

1

It is a backtracking algorithm. In recursion rec(arr, total, i), it picks the last element arr[i] in rest array, and here are two main situations:

use arr[i]: rec(arr, total-arr[i], i-1)
not use arr[i]: rec(arr, total, i-1), and when arr[i] > total of course you can only not use it.

and we must have terminate condition for recursion, that is:

[success] find the subarray equal to total: if total == 0: return 1
[failed] reach the head: if i < 0: return 0

Hope I make it clear, and comment if you have further questions. : )

edited Apr 12, 2019 at 13:45

answered Apr 12, 2019 at 13:36

recnac

3,7746 gold badges27 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Maged Saeed Over a year ago

Nicely explained!

recnac Over a year ago

Thanks, forgive my poor english : ) @MagedSaeed

Collectives™ on Stack Overflow

Python understanding recursive program

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related