# Speeding up subset sum implementation

Important fact: the number of the input is greater than 1. How do I use this fact to speed up this solution?

public class subSetSumR{
// Solving Subset sum using recursion

public static boolean subSetSumRecur(int [] mySet, int n, int goal){
if (goal ==0){
return true;}
if ((goal<0)|(n>=mySet.length))
return false;
if (subSetSumRecur(mySet,n+1,goal - mySet[n])){
System.out.print(mySet[n]+" ");
return true;}
if (subSetSumRecur(mySet,n+1,goal))
return true;
return false;
}


At times to speed up a recursion you can use memoization to cache the results of your previous known calculations, trading memory for speed. (Memoization is slightly different to dynamic programming.)

A memoized function "remembers" the results corresponding to some set of specific inputs. Subsequent calls with remembered inputs return the remembered result rather than recalculating it, thus eliminating the primary cost of a call with given parameters from all but the first call made to the function with those parameters.

Here's an example, after I took the liberty to simplify the number of arguments a bit for sake of clarity,

public static Map<List<Integer>, Boolean> cache = new HashMap<List<Integer>, Boolean>();

public static boolean subSetSum(List<Integer> S, int sum) {
if (sum == 0) return true;
if (S.size() == 0 || sum < 0) return false;

List<Integer> key = new ArrayList<Integer>(S); // composite (set, sum) memoization key
// let x be the first element of S, then there is either a solution with
// the set S - {x} without the first element considered, or there is a
// solution where x is accounted for, ie with the set S - {x} and sum - x
if (!cache.containsKey(key)) {
List<Integer> forwardSet = S.subList(1, S.size());
cache.put(key, subSetSum(forwardSet, sum) || subSetSum(forwardSet, sum - S.get(0)));
}
return cache.get(key);
}
// Example: subSetSum(Arrays.asList(new Integer[] { -7, -3, -2, 5, 8 }), 1);


Note the caveat that the example outlines the trade-off described above, it may or may not be faster than your specific example. For example, notice that the list of integers that constitutes the key is cloned, which is suboptimal.

• thanks, but I don't understand python – user3527406 Apr 22 '14 at 13:43
• @user3527406 Also see this question: codereview.stackexchange.com/questions/45910/… . The answers has some guidelines on how to remember previous calculations. – Simon Forsberg Apr 22 '14 at 14:12
• @user3527406 You should still have a look at the Python code and maybe learn a bit about Python. IMHO as a programmer you should always be able to understand the basics of any programming language using a bit of common sense (and a reference manual). – RoToRa Apr 22 '14 at 21:30