Quite confused about this problem [Partition Equal Subset Sum]

Hi! For the following question, I wrote the code below. When filling in the hash table, all other solutions shared by people and also by leetcode team use both index and sum as key for hash table. For example, m.set(`${idx}-${sum}`, res) instead of m.set(sum, res). However, my solution passes all the tests even without including index as part of key. Can you please explain why index should be included as part of key?

416. Partition Equal Subset Sum

Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

link: https://leetcode.com/problems/partition-equal-subset-sum/

Code:

var canPartition = function(nums) {
    let sum = nums.reduce((acc,cur) => acc + cur);
    if (sum % 2 === 1) {
        return false;
    }
    sum /= 2;
    let memo = new Map();
    return dfs(nums, sum, 0, memo);
};

const dfs = (nums, sum, idx, memo) => {
    if (sum === 0) {
        return true;
    }
    if (sum < 0 || idx === nums.length) {
        return false;
    }
    if (memo.has(sum)) {
        return memo.get(sum);
    }
    let res = dfs(nums, sum - nums[idx], idx + 1, memo) ||
            dfs(nums, sum, idx + 1, memo);
    memo.set(sum, res);
    return res;
}

Comments (0)