## 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*(*n*2^{n}). 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*(*n*2^{n}) time complexity, but builds up the solution in stages. A matrix has *n* rows and 2^{n} 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.

Pages: 1 2

[…] 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):

Python 2.7 solution:

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;

}

}