The Problem :

Given a set l of non-negative integers, and a value sum , determine if there is a subset of the given set with sum equal to given sum.

Examples : 

Input : N = 6 arr[] = {3, 34, 4, 12, 5, 2} sum = 9

Output: 1

Explanation : Here there exists a subset with sum = 9, 4+3+2 = 9.

Input : N = 6 arr[] = {3, 34, 4, 12, 5, 2} sum = 30

Output : 0

Explanation : There is no subset with sum 30.

The Solution :

Obviously we could think of a bruteforce approach where we list all the subsets and check if any of them works.

However that would be too slow as we would need to enumerate all the 2^N subsets (with N the given set's number of elements) and checking for each one if the elements add up to the given sum.

But a more optimized solution would be :

If there exists a solution to the problem , we know that if we take an element x from l it either is in the solution or not so of the following calls must return true :

• subset (l\{x}, sum-x) : if x is in the solution subset then there is a subset of l without x which sums up to sum-x
• subset (l\{x},sum): if x is not in the solution subset then there is a subset of l without x which sums up to sum

These are the recursive calls we will need in our function, but we will also need base cases :

• if sum == 0 then the empty set is a solution so we can return True
• else if l is empty (and sum ≠ 0) we must return False.

And there we have our algorithm !

Code

def subset(l, s):
    # We first check for the base cases
    if s == 0: # if the sum is 0 we can return True
        return True
    elif not l: # else if the set is empty we can return False
        return False
    else:
        x, *t = l
        
        """The * operator is used for unpacking the head and tail 
        of the list l meaning that the first element of l is stored 
        in x and the rest is in t"""
        
        return subset(t, s-x) or subset(t, s) #these are the recursive calls 


"""the call subset([3, 34, 4, 12, 5, 2],30) returns False 
and subset([3, 34, 4, 12, 5, 2],9) returns True"""