CODEWITHSUNDEEP
algorithmdynamic-programming
user6575289
user6575289

Reputation:

Space optimization of DP solution of Subset sum?

I was doing the subset sum problem for positive numbers. In the typical DP solution we use a 2D DP table of the form table[n+1][sum+1] where n is the number of elements in the set and sum is the target sum. Now i wanted to optimize it to use only one row as all the rows use results of previous row. For that i made a solution as:

boolean DP[] = new boolean[sum+1];
DP[0] = true;
for(int i = 0; i < arr.length; i++) {
    for(int j = arr[i]; j <= sum; j++) {
        DP[j] = DP[j] || DP[j-arr[i]];
    }
}
return DP[sum];

This code fails some test cases. However if i change the inner loop to iterate backwards as:

for(int j = sum; j >= arr[i]; j--)

Then this code passes all the test cases. I am not able to figure out the difference that iterating backwards has made. I would appreciate explanation.

Upvotes: 1

Views: 502

Answers (1)

Pham Trung
Pham Trung

Reputation: 11284

Simple example to help you understand

arr = {1, 4}, sum = 7

In case of iterating forward, first iteration, i = 0

dp[0] = true
for (int j = arr[0]; j <= sum; j++){

}

Here are the step inside this loop:

dp[1] = dp[1] || dp[1 - 1]; //true as dp[0] = true
dp[2] = dp[2] || dp[2 - 1]; // also true, as previous step, we update dp[1] = true
....
dp[7] = dp[7] || dp[7 - 1]; // true for similar reason

So, for the first iteration, all elements are true

In case of iterating backward, first iteration, i = 0

dp[0] = true
for (int j = sum; j >= arr[0]; j--){

}

Here are the step inside this loop:

dp[7] = dp[7] || dp[7 - 1]; //false 
dp[6] = dp[6] || dp[6 - 1]; // also false,
....
dp[1] = dp[1] || dp[1 - 1]; // true as dp[0] = true

So, for the first iteration, all except dp[1] and dp[0] = true, which is what we want.

Upvotes: 2

Related Questions