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=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, Boolean> cache = new HashMap, Boolean>();

public static boolean subSetSum(List S, int sum) {
    if (sum == 0) return true;
    if (S.size() == 0 || sum  key = new ArrayList(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 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.

StackExchange Code Review Q#47878, answer score: 8