CODEWITHSUNDEEP
pythonpython-3.xrecursion
Gaurang Shah
Gaurang Shah

Reputation: 12900

Python understanding recursive program

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.

Upvotes: 1

Views: 51

Answers (1)

recnac
recnac

Reputation: 3744

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:

  1. use arr[i]: rec(arr, total-arr[i], i-1)
  2. 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:

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

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

Upvotes: 1

Related Questions