Subset Sum
March 27, 2012
The subset-sum problem asks you to find the subset of a set of integers that sums to a given target; for instance, given the set {267 439 869 961 1000 1153 1246 1598 1766 1922} and target 5842, the subset {869 961 1000 1246 1766} sums to 5842. This is a well-known NP problem, and the standard solution via dynamic programming takes time O(n2n). The basic idea is straight forward: generate a list of subsets, compute the sum of each, and return the one that sums to the target.
The dynamic programming solution has the same O(n2n) time complexity, but builds up the solution in stages. A matrix has n rows and 2n columns; the rows are marked with the n input values, the columns are marked with the various subset-sums, and each cell contains a list of items from the n values up to the current row that sums to the column total. We’ll look at an example: find the subset of items from {1 -3 4 2} that sums to 0. After the first element of the list is considered, the first row has two columns, the null column that we ignore and the column 1:
| 1 | |
| 1 | 1 |
With the second row, there are four columns: the null column that we ignore, and columns -3, 1, and 2:
| -3 | 1 | 2 | |
| 1 | 1 | ||
| -3 | -3 | 1 | -3 1 |
When we add the third row, there are eight columns: the null column that we ignore, the six columns -3, -2, 1, 2, 4, and 5, and a hidden column for 1, which can be formed in two different ways, as 1 by itself and as the sum of -3 and 4:
| -3 | -2 | 1 | 2 | 4 | 5 | |
| 1 | 1 | |||||
| -3 | -3 | -3 1 | 1 | |||
| 4 | -3 | -3 1 | 1 | -3 1 4 | 4 | 1 4 |
When we add the fourth row, there are sixteen columns, but only eleven appear in the table: -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, and 7. We ignore the null column, and there are four hidden columns corresponding to the following sum-pairs, only one of which appears in the table (it doesn’t matter which): 1 = -3 + 4, 2 = -3 + 1 + 4, 1 + 2 = -3 + 2 + 4, and 4 = -3 + 1 + 2 + 4:
| -3 | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| 1 | 1 | ||||||||||
| -3 | -3 | -3 1 | 1 | ||||||||
| 4 | -3 | -3 1 | 1 | -3 1 4 | 4 | 1 4 | |||||
| 2 | -3 | -3 1 | -3 2 | -3 1 2 | 1 | -3 1 4 | 1 2 | 4 | 1 4 | 2 4 | 1 2 4 |
The solution is the subset {-3 1 2}. I apologize for my lack of table-fu.
Your task is to write a function that solves the subset-sum problem. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
[…] today’s Programming Praxis problem, our goal is to find all the subsets of a list that sum up to a given […]
My Haskell solution (see http://bonsaicode.wordpress.com/2012/03/27/programming-praxis-subset-sum/ for a version with comments):
subsetSum :: Num a => a -> [a] -> [[a]] subsetSum n xs = [ns | (total, ns) <- subsets xs, total == n] where subsets = foldr (\x a -> (x, [x]) : map (\(t, ns) -> (t+x, x:ns)) a ++ a) []Python 2.7 solution:
from itertools import takewhile def partial_sum(numset, target): sums = {} for n in takewhile(lambda _: target not in sums, numset): sums.update( ( k + n, v + [n] ) for k,v in sums.items() + [ (n, [n]) ] ) return sums.get(target, [])Should work under Python 3 if “sums.items()” is changed to “list(sums.items())” — although I haven’t tested it.
In the problem example, the second table (with three rows) has a typo in row 3, column 2: the -1 should be -3
Mirko: Fixed. Thanks.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class Subset {
ArrayList solution=new ArrayList();
ArrayList number_list=new ArrayList();
int target;
public void problem5()
{
try
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println(“Input the number of elements in set”);
int length=Integer.parseInt(br.readLine());
for(int count=0;count<length;count++)
{
System.out.println("Enter the subset elements");
int number=Integer.parseInt(br.readLine());
number_list.add(number);
}
System.out.println("Enter the target :");
target=Integer.parseInt(br.readLine());
for(int number_export:number_list)
{
calculate(Integer.toString(number_export));
}
System.out.println(solution);
}
catch(IOException ioe)
{
ioe.printStackTrace();
}
}
public void calculate(String number)
{
String number_sequence[]=number.split(",");
if(present(number))
{
return;
}
else
{
int sum=0;
for(int counter=0;countersum)
{
for(int number_attach:number_list)
{
if(!numberPresent(number,number_attach))
{
calculate(number+”,”+number_attach);
}
}
}
else
{
return;
}
}
}
public boolean present(String number)
{
ArrayList test_number_ref=new ArrayList();
String number_sequence[]=number.split(“,”);
for(int count=0;count<number_sequence.length;count++)
{
test_number_ref.add(number_sequence[count]);
}
for(String number_present:solution)
{
String number_present_list[]=number_present.split(",");
ArrayList test_number=new ArrayList(test_number_ref);
if(number_present_list.length==test_number.size())
{
for(int count=0;count<number_present_list.length;count++)
{
int counter=0;
while(counter<test_number.size())
{
if(number_present_list[count].equals(test_number.get(counter)))
{
test_number.remove(counter);
counter–;
}
counter++;
}
}
if(test_number.size()==0)
return true;
}
}
return false;
}
public boolean numberPresent(String numberlist,int number)
{
String number_value[]=numberlist.split(",");
for(int count=0;count<number_value.length;count++)
{
if(Integer.parseInt(number_value[count])==number)
{
return true;
}
}
return false;
}
}
[…] than the square root of n. There are several ways to solve the subset sum problem. The standard solution uses dynamic programming. Another solution splits the problem space into two parts. Both solutions […]