The Bruteforce approach to find the shortest subsequence length for a given sum is giving the correct 2,2,9 outputs for the inputs given in the main method but when memoized getting wrong output 3,3,9. Can anyone help with this please? Thanks.

class ShortestSubsequenceWithSum {    
  public static int shortestSubsequenceWithSum(int[] num, int s, int cnt, Integer []dp) {
    if(s == 0){
      return cnt;
    }
    if(s < 0){
      return Integer.MAX_VALUE;
    }
    if(dp[s] != null){
      return dp[s];
    }
    int res = Integer.MAX_VALUE;
    for(int i=0; i<num.length; i  ){
      int rem = s - num[i];
      int ways = shortestSubsequenceWithSum(num, rem, cnt  1, dp);
      res = Math.min(res, ways);
      dp[s] = res;
    }
    // System.out.println("Returning value at @ "   s);
    return dp[s];
  }
  
  public static void main(String[] args) {
    int[] num = {1, 1, 2, 3};
    Integer dp[] = new Integer[5 1];
    System.out.println(shortestSubsequenceWithSum(num, 5,0, dp));
    num = new int[]{1, 2, 7, 1};
    dp = new Integer[9 1];
    System.out.println(shortestSubsequenceWithSum(num, 9,0, dp));
    num = new int[]{1};
    dp = new Integer[9 1];
    System.out.println(shortestSubsequenceWithSum(num, 9,0, dp));
  }
}

CodePudding user response：

The problem here is that the way your recursive method works at present isn't amenable to memoization.

It looks like you are using your dp array to store the currently-known minimum count of numbers required to make a total. So dp[5] will be the minimum count of numbers required to make a total of 5. If dp[5] = 3 then you have found a way to make a total of 5 from three numbers, but not yet found a way to make 5 from fewer than three numbers.

Your method shortestSubsequenceWithSum presently returns the minimum count of numbers required to reach the total plus the number of recursive calls currently made. If you want to use memoization you will have to adjust this method to return the minimum count of numbers required to reach the total, regardless of how many levels of recursion there have so far been.

The changes you will need to make are:

• In the handling for the case s == 0, return 0 rather than cnt. This represents being able to make a total of 0 from zero numbers.
• Change the line dp[s] = res to dp[s] = res 1. res contains the (minimum) count of numbers that make up s - num[i] for each value of i so far, so we add 1 for choosing num[i] in a combination that adds up to s.

These should be enough to get your code working. However, you can in fact move the line dp[s] = res 1 immediately outside the for loop: we may as well wait for the final value of res before assigning it to dp[s]. You can also remove the parameter cnt from your method shortestSubsequenceWithSum, and all the calls to this method, as this parameter isn't being used any more.

This should leave you with the following:

    /**
     * Returns the minimum count of numbers from the given array that can
     * make up a total. The same number can be chosen multiple times.
     * @param num The numbers that can be chosen from.
     * @param s The total to reach.
     * @param dp An array that memoizes pre-computed values of this method.
     * @return The minimum count of numbers from 'num' that totals 's'.
     */
    public static int shortestSubsequenceWithSum(int[] num, int s, Integer []dp) {
        if(s == 0){
            return 0;
        }
        if(s < 0){
            return Integer.MAX_VALUE;
        }
        if(dp[s] != null){
            return dp[s];
        }
        int res = Integer.MAX_VALUE;
        for(int i=0; i<num.length; i  ){
            int rem = s - num[i];
            int ways = shortestSubsequenceWithSum(num, rem, dp);
            res = Math.min(res, ways);
        }
        dp[s] = res   1;
        // System.out.println("Returning value at @ "   s);
        return dp[s];
    }

---

Finally, I'll note that this code does not handle the case that there are no combinations that add up to the total. I'll leave fixing that as an exercise for you, see below for an example test case:

int[] num = {2, 4, 6};
Integer dp[] = new Integer[5 1];
System.out.println(shortestSubsequenceWithSum(num, 5, dp));