Subset Sum Problem Implementation with Python

A version of the subset sum problem is to find a subset of S whose sum is as large as possible, but no larger than t with S = {x1, x2, …, xn} is a set of positive integers, and t is a target.

Let’s review a few of the possible use cases for this problem:

In transportation, given various packages of different weights (S is a set of weights, in say pounds) and a truck that can carry t pounds, we want the truck to carry as many weights as possible without being overloaded. So we need to pick the best subset of the packages to use the capacity of the truck in the best way.

For a radio host, given a number of songs and commercials (S is a set of duration of these songs and commercials, in say seconds), and the length of the show in t seconds, she/he wants to play a combination of songs and commercials as close to t second as possible. So we need to pick again the best subset of the songs and commercials having the best fit with the program duration.

Let’s look some very simple subset problem examples:

So how do we get these subsets in order to find the best fit?

Let’s call Col for a variable list to hold all the possible subsets and we already know what S and t is, the pseudo code to obtain the subsets one by one would be like that: