# How to Solve the Subset Sum Problem Using Python

*12 May 20235 min readby*

**Crawayito**

## 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"""
```