ZeeshanAli-0704

Posted on

# Subset sum equal to target (DP- 14)

``````// 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 {