4

The following page contains a 2-D DP solution to the "subset sum" problem:

https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/SubsetSum.java

Core method:

boolean[][] T = new boolean[input.length + 1][total + 1];
for (int i = 0; i <= input.length; i++) {
    T[i][0] = true;
}

for (int i = 1; i <= input.length; i++) {
    for (int j = 1; j <= total; j++) {
        if (j - input[i - 1] >= 0) {
            T[i][j] = T[i - 1][j] || T[i - 1][j - input[i - 1]];
        } else {
            T[i][j] = T[i-1][j];
        }
    }
}
return T[input.length][total];

I'm trying to reduce the space usage by replacing the 2-D array w/ a 1-D one like this:

boolean[] T = new boolean[sum + 1];     
T[0] = true;      

for (int i = 1; i <= input.length; i++) {
    for (int j = 1; j <= sum; j++) {
        if (j - input[i - 1] >= 0) {
            T[j] = T[j] | T[j - input[i - 1]]; //not using ||
        } 
    }
}
return T[sum];

and I failed miserably: it's returning true for any inputs. Can someone point out the problem?

1 Answer 1

3

The Topological ordering of your solution is incorrect.

If you change the second loop to for (int j = sum; j >= 1; j--) it should work.

It happens because when you move forward in the second loop, you are also considering solutions that were solved by the current index i and therefore including the current element multiple times in the solution instead of only including it once.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.