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.
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 […]