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.

About these ads

Pages: 1 2

6 Responses to “Subset Sum”

  1. [...] today’s Programming Praxis problem, our goal is to find all the subsets of a list that sum up to a given [...]

  2. 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) []
    
  3. Mike said

    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.

  4. mirko said

    In the problem example, the second table (with three rows) has a typo in row 3, column 2: the -1 should be -3

  5. programmingpraxis said

    Mirko: Fixed. Thanks.

  6. Ankit Thakur said

    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;
    }

    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 574 other followers

%d bloggers like this: