subset sum

class Solution {

    static Boolean isSubsetSum(int arr[], int sum) {
        Boolean[][] dp = new Boolean[arr.length][sum + 1]; // Memoization table
        return helper(dp, arr, sum, arr.length - 1);
    }

    public static Boolean helper(Boolean[][] dp, int[] arr, int sum, int idx) {
        if (sum == 0) {
            return true;
        }
        if (idx < 0 || sum < 0) {
            return false;
        }

        // If already computed, return stored result
        if (dp[idx][sum] != null) {
            return dp[idx][sum];
        }

        // If the current element is greater than sum, exclude it
        boolean exclude = helper(dp, arr, sum, idx - 1);
        boolean include = false;
        if (arr[idx] <= sum) {
            include = helper(dp, arr, sum - arr[idx], idx - 1);
        }

        // Store and return the result
        return dp[idx][sum] = include || exclude;
    }
}