Subset Sum Problem

function isSubsetSumRecursive(set, n, sum) {
    // Base Cases
    if (sum === 0) return true;
    if (n === 0) return false;
 
    // If last element is greater than sum, ignore it
    if (set[n - 1] > sum) {
        return isSubsetSumRecursive(set, n - 1, sum);
    }
 
    // Check if sum can be obtained by either including or excluding the last element
    return isSubsetSumRecursive(set, n - 1, sum) || 
           isSubsetSumRecursive(set, n - 1, sum - set[n - 1]);
}

function isSubsetSumMemoization(set, n, sum) {
    // Create a 2D array initialized with null
    const memo = Array.from({ length: n + 1 }, () => new Array(sum + 1).fill(null));
 
    function helper(i, s) {
        if (s === 0) return true;
        if (i === 0) return false;
 
        if (memo[i][s] !== null) return memo[i][s];
 
        if (set[i - 1] > s) {
            memo[i][s] = helper(i - 1, s);
        } else {
            memo[i][s] = helper(i - 1, s) || helper(i - 1, s - set[i - 1]);
        }
 
        return memo[i][s];
    }
 
    return helper(n, sum);
}

function isSubsetSumTabulation(set, n, sum) {
    const dp = Array.from({ length: n + 1 }, () => new Array(sum + 1).fill(false));
 
    // Base case: If sum is 0, then answer is true (empty subset)
    for (let i = 0; i <= n; i++) {
        dp[i][0] = true;
    }
 
    // Base case: If sum is not 0 and set is empty, then answer is false
    for (let j = 1; j <= sum; j++) {
        dp[0][j] = false;
    }
 
    // Fill the table in bottom-up manner
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= sum; j++) {
            if (set[i - 1] <= j) {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - set[i - 1]];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
 
    return dp[n][sum];
}

function isSubsetSumSpaceOptimized(set, n, sum) {
    // dp[j] will store if sum j is possible
    const dp = new Array(sum + 1).fill(false);
    dp[0] = true; // Base case: sum 0 is always possible
 
    for (let i = 0; i < n; i++) {
        // Traverse sum from right to left
        for (let j = sum; j >= set[i]; j--) {
            if (dp[j - set[i]] === true) {
                dp[j] = true;
            }
        }
    }
 
    return dp[sum];
}
 
// Driver code
const set = [3, 34, 4, 12, 5, 2];
const sum = 9;
const n = set.length;
console.log("Is there a subset with sum 9?", isSubsetSumSpaceOptimized(set, n, sum));
// Output: Is there a subset with sum 9? true