Subset Sum

March 27, 2012

Instead of a matrix, we use a hash table; that way we don’t have to figure out all the sums ahead of time. Here’s the code:

(define (subset-sum xs t)
  (let ((h (make-hash identity = #f 99991)))
    (let loop1 ((xs xs))
      (if (null? xs) #f
        (let loop2 ((ys (cons (cons 0 (list)) (h 'enlist))))
          (cond ((null? ys) (loop1 (cdr xs)))
                ((= (+ (car xs) (caar ys)) t)
                  (cons (car xs) (cdar ys)))
                (else (h 'insert (+ (car xs) (caar ys))
                                 (cons (car xs) (cdar ys)))
                      (loop2 (cdr ys)))))))))

The outer loop, on xs, runs over each input element; if it runs out of elements without finding the target, it reports failure. The inner loop, on ys, runs over each sum of the prior row, plus 0 (which causes the element itself to be part of the next row), producing the next row; it saves the current row in ys with the enlist message to the hash table, goes on to the next row when the current row is exhausted, and stops as soon at is finds the target sum. Here’s the function in action:

> (subset-sum '(267 439 869 961 1000 1153 1246 1598 1766 1922) 5842)
(1766 1246 1000 961 869)

We used hash tables and the identity function from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/3ZLhrqEs.

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 630 other followers

%d bloggers like this: