// 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();
For further actions, you may consider blocking this person and/or reporting abuse
Top comments (0)