Number of subsets with zero sum - interpretation of the result

Question

The code below is about dynamic programming with the subset zero sum algorithm.

In other words, it informs how many subsets sum to zero when adding their elements.

However, if the set is [2, -2], the result will be 2, as there are two subsets with a sum of zero, the {} (empty set) and {2, -2}.

But if we change the set to [2, 2], the result remains 2.

What interpretation is this, as for me, it should be 1?

The JavaScript code was taken from the website geeksforgeeks

    const arr = [2, 2];
    const n = arr.length;
    const maxSum = 3;
    
    const dp = new Array(n + 1);
    for (let i = 0; i <= n; i++) {
      dp[i] = new Array(2 * maxSum + 1).fill(0);
    }
    
    for (let i = 0; i <= n; i++) {
      dp[i][maxSum] = 1;
    }
    
    for (let i = 1; i <= 2 * maxSum; i++) {
      dp[0][i] = 0;
    }
    
    for (let i = 1; i <= n; i++) {
      for (let j = -maxSum; j <= maxSum; j++) {
        const val = arr[i - 1];
        if (j - val + maxSum >= 0 && j - val + maxSum <= 2 * maxSum) {
          dp[i][j + maxSum] += dp[i - 1][j - val + maxSum];
        }
    
        if (j + maxSum >= 0 && j + maxSum <= 2 * maxSum) {
          dp[i][j + maxSum] += dp[i - 1][j + maxSum];
        }
      }
    }
    console.log(dp)
    console.log(dp[n][maxSum])

Answer 1

The code provided in the previous response works for floats and negative numbers; however, it has a problem. If the list has 20 items, it will result in a stack overflow with over a million sums.

To address this issue, a dictionary named "check" was added, where the key is the result of the sum. This ensures that there are no repeated sums in the list. This solution already solves a significant part of the problem. However, to further improve it, conditions were added to accept or reject numbers.

The positive and negative values were summed separately. If the positive values are greater than the negatives, any positive number greater than the negative ones will be discarded from the list because it will never result in zero with those numbers.

Now, if the negative values are greater than the positives, any negative number greater than the positives will be discarded because such numbers will never result in zero.

By doing this, the list is significantly reduced to find the subset that sums to zero.

    function subsetSumZero(rawList) {
        let sum = [];
        let check = {};
        let list = [];

        let positiveList = [];
        let negativeList = [];

        // Separate positive and negative numbers
        for (let i = 0; i < rawList.length; i++) {
            const element = rawList[i];
            if (element > 0) {
                positiveList.push(element);
            } else {
                negativeList.push(element);
            }
        }

        // Sum the numbers in the lists
        let sumPositives = positiveList.reduce((accumulator, value) => {
            if (typeof value === 'number') {
                return accumulator + value;
            } else {
                return accumulator;
            }
        }, 0);

        let sumNegatives = negativeList.reduce((accumulator, value) => {
            if (typeof value === 'number') {
                return accumulator + value;
            } else {
                return accumulator;
            }
        }, 0);

        if (sumPositives > sumNegatives) {
            for (let i = 0; i < positiveList.length; i++) {
                const element = positiveList[i] * -1;
                if (element >= sumNegatives) {
                    list.push(positiveList[i]);
                }
            }
            list.push(...negativeList);
        } else if (sumPositives < sumNegatives) {
            for (let i = 0; i < negativeList.length; i++) {
                const element = negativeList[i] * -1;
                if (element <= sumPositives) {
                    list.push(negativeList[i]);
                }
            }
            list.push(...positiveList);
        } else {
            return true; // If the sum of positives is equal to the sum of negatives, the result is zero
        }

        if (sum.length === 0) {
            sum.push(list[0]);
            check[list[0]] = true;
        }

        for (let i = 1; i < list.length; i++) {
            if (!check.hasOwnProperty(list[i])) {
                sum.push(list[i]);
                check[list[i]] = true;
            }

            let temp = [];

            for (let j = 0; j < sum.length - 1; j++) {
                // Each sum here is the sum of a subset because sum[j] represents
                // a subset. When adding it to list[i], a new subset is created. 
                // Therefore, I am summing all the existing subsets in the list.
                let summation = sum[j] + list[i];

                if (summation === 0) {
                    return true;
                }

                if (!check.hasOwnProperty(summation)) {
                    temp.push(summation);
                    check[summation] = true;
                }
            }
            sum.push(...temp);
        }
        return false;
    }

    const list = [10, 100, 100, 100, 100, 100, 100, 20, 200, 3, 300, 40, 40, 50, 50, 50, 57, 597.53, -6.68, 6.68];
    const decision = subsetSumZero(list)

Answer 2

Dynamic Programming - DP

The code I posted in the question doesn't work with DP - Tabulation, it only works with Memoization, which is available on the website geeksforgeeks. If the answer is greater than 1, it means there is a subset that sums to zero, but it doesn't work for floating-point numbers.

However, I managed to create decision-making code to determine if the set has any summation that equals zero, and it's implemented using DP - Tabulation.

The code works for both negative integers and floating-point numbers.

    function subsetSumZero(list, target) {
        let sum = [];

        if (sum.length === 0) {
            sum.push(list[0]);
        }

        for (let i = 1; i < list.length; i++) {
            sum.push(list[i]);
            let temp = [];

            for (let j = 0; j < sum.length - 1; j++) {
                let summation = sum[j] + list[i];

                if (summation === target) {
                    return true;
                }

                temp.push(summation);
            }
            sum.push(...temp);
        }

        return false;
    }

    const list = [-10.07, 100, -13579.03, -4, 13589.1];
    const target = 0
    const decision = subsetSumZero(list, target)