Speeding up subset sum implementation

Question

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

Answer 1

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
    key.add(sum);
    // 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.