<h2 style="text-align:center;">The Problem :</h2>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.<h3>Examples :&nbsp;</h3>Input : N = 6 arr[] = {3, 34, 4, 12, 5, 2} sum = 9Output:&nbsp;1Explanation : Here there exists a subset with sum = 9, 4+3+2 = 9.Input : N = 6 arr[] = {3, 34, 4, 12, 5, 2} sum = 30Output :&nbsp;0Explanation : There is no subset with sum 30.<h2 style="text-align:center;"> The Solution :</h2>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 :<ul><li>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</li><li>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</li></ul>These are the recursive calls we will need in our function, but we will also need base cases :<ul><li>if sum == 0 then the empty set is a solution so we can return True</li><li>else if l is empty (and sum ≠ 0) we must return False.</li></ul>And there we have our algorithm !<h2 style="text-align:center;">Code</h2><pre><code class="language-python">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"""</code></pre>

How to Solve the Subset Sum Problem Using Python