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&lt;0)|(n&gt;=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&lt;List&lt;Integer&gt;, Boolean&gt; cache = new HashMap&lt;List&lt;Integer&gt;, Boolean&gt;();

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

    List&lt;Integer&gt; key = new ArrayList&lt;Integer&gt;(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&lt;Integer&gt; 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.