educative.io

Educative

Memoization solution failing for last test case

Here is my code, can you tell me what I am doing wrong, my approach is slightly different to the solution. I am starting from 0th index and adding up the elements or ignoring them.
public static long countSubsetSum(int[] nums, int integer) {

    // Replace this placeholder return statement with your code
    int sum = Arrays.stream(nums).sum();
    int [][] dp = new int[nums.length][sum];
    for(int i = 0; i < nums.length; i++){
        Arrays.fill(dp[i], -1);
    }

    int max = 0;
    helper(0, 0, integer, nums, dp);
    for(int i = 0; i < dp.length; i++){
        for(int j = 0; j < dp[i].length; j++){
            if(dp[i][j] != -1){
                max = Math.max(max, dp[i][j]);
            }
        }
    }

    return max;
}

public static int helper(int index, int sum, int target, int [] nums, int [][] dp){
    if(sum == target){
        return 1;
    }

    if(index >= nums.length || sum > target){
        return 0;
    }

    if(dp[index][sum] != -1){
        return dp[index][sum];
    }

    dp[index][sum] = helper(index + 1, sum + nums[index], target, nums, dp) + helper(index + 1, sum, target, nums, dp);

    return dp[index][sum];
}

Course: Grokking Dynamic Programming: A Deep Dive Using Java - Learn Interactively
Lesson: Count of Subset Sum

1 Like

Hello @Abhinav1,

Your code is partially correct, but the main issue lies within the return types, i.e., the main function is expecting a long return type, however your helper method is returning an int return type.

The mismatch between the results of the last test case is occurring because the value 3652001142013404 doesn’t fit in int. I’ve modified the code accordingly, you can see and test it on the provided coding widget.

import java.util.*;

public class SubsetSum {
    public static long countSubsetSum(int[] nums, int target) {
        // Changed dp array to long
        long[][] dp = new long[nums.length][Arrays.stream(nums).sum() + 1];
        for (int i = 0; i < nums.length; i++) {
            Arrays.fill(dp[i], -1);
        }

        long max = 0;
        helper(0, 0, target, nums, dp);
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                if (dp[i][j] != -1) {
                    max = Math.max(max, dp[i][j]);
                }
            }
        }

        return max;
    }

    // Changed return type to long
    public static long helper(int index, int sum, int target, int[] nums, long[][] dp) {
        if (sum == target) {
            return 1;
        }

        if (index >= nums.length || sum > target) {
            return 0;
        }

        if (dp[index][sum] != -1) {
            return dp[index][sum];
        }

        // Storing the result in long type variable
        dp[index][sum] = helper(index + 1, sum + nums[index], target, nums, dp) 
                         + helper(index + 1, sum, target, nums, dp);

        return dp[index][sum];
    }
}

I hope this will help you and clarifies what the main issue was. Please feel free to share further feedback and suggestions. We’d be happy to help. Thanks!

Happy learning!