// Define the function to solve the problem
function solveUtil(ind, arr, dp, target) {
    // Check if the result for this index is already calculated
    if (dp[ind][target]) {
        return dp[ind][target];
    }

    // Base cases
    if (target === 0) {
        return true;
    }
    if (ind === 0) {
        return arr[ind] === target;
    }

    // Calculate the maximum value by either picking or not picking the current element
    let nonPick = solveUtil(ind - 1, arr, dp, target);
    let pick = false;
    pick =
        arr[ind] <= target ? solveUtil(ind - 1, arr, dp, target - arr[ind]) : false;

    // Store the result in the DP array and return it
    dp[ind][target] = Math.max(pick, nonPick);
    return Math.max(pick, nonPick);
}

// Main function to solve the problem
function subsetSumToK(n, k, arr) {
    // Initialize a DP array with -1
    const dp = new Array(n);
    for (let i = 0; i < n; i++) {
        dp[i] = new Array(k + 1).fill(false);
    }

    // Call the solveUtil function with the last index
    return solveUtil(n - 1, arr, dp, k);
}

// Main program
function main() {
    const arr = [1, 2, 3, 4];
    const k = 10;
    const n = arr.length;

    if (subsetSumToK(n, k, arr)) {
        console.log("Subset with given target found");
    } else {
        console.log("Subset with given target not found");
    }
}

// Call the main function to run the program
main();