CODEWITHSUNDEEP
algorithmdynamic-programming
KamiWar
KamiWar

Reputation: 51

Partition Equal Subset Sum

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

So the formula that allows one to calculate dp[i][j], where if there is a combination out of the first i'th elements that sum up to j is:

dp[i][j] = dp[i - 1][j - nums[i - 1]] || dp[i - 1][j];

The first half before the OR operator represents what happens when we SELECT the I'th Element.

My question is why is it j - nums[i - 1] and NOT j - nums[i].

Shouldn't we minus the current sum(j) by the current 'weight' (nums[i]) of the i'the element and see if the first i - 1 elements can sum up to it?

Why do we minus the value of the previous element?

Upvotes: 0

Views: 450

Answers (1)

MBo
MBo

Reputation: 80197

Note that table contains n+1 rows, and we can see in more full code that i index goes from 1 to n, so nums[i-1] refers to zero-based items of nums[] in range of index 0..n-1

   for (int i = 1; i < n+1; i++) {
        for (int j = 1; j < sum+1; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= nums[i-1]) {
                dp[i][j] = (dp[i][j] || dp[i-1][j-nums[i-1]]);
            }
        }
    }

Upvotes: 1

Related Questions