CODEWITHSUNDEEP
javaalgorithmdynamic-programming
IUnknown
IUnknown

Reputation: 9809

subset sum through DP

There is a concise explanation on this approach at http://comproguide.blogspot.in/2013/10/subset-sum-problem.html
However,I enumerate this algorithm through a small exercise to find sub-sets in {1,2,3,4} that sum to 4.

I notice that the cells {1,1},{2,2} return a false.

Did I understand the logic wrong?
Or does the algorithm does not consider the set to be a subset of itself?

I would have expected {1,1} to return a true as 1 adds upto itself.

Upvotes: 0

Views: 145

Answers (2)

Ravi Chandra
Ravi Chandra

Reputation: 687

I am the author of the post. What ever output shown by @fgb looks correct. I don't see any problem with the code. Is there anything wrong with my explanation?

Upvotes: 0

fgb
fgb

Reputation: 18569

{1} should count as a subset that sums to 1. I've added some output to the program to show the table:

public class SubsetSum {
    public static void main(String[] args) {
        int [] array = { 1, 2, 3, 4 };
        hasSum(array, 4);
    }

    public static boolean hasSum(int [] array, int sum) {
        int len = array.length;
        boolean[][] table = new boolean[sum+1][len+1];
        for(int i = 0; i <= len; i++) table[0][i] = true;
        for(int i = 1; i <= sum; i++) table[i][0] = false;
        for(int i = 1; i <= sum; i++) {
            for(int j = 1; j <= len; j++) {
                table[i][j] = table[i][j-1];
                if(!table[i][j] && i >= array[j-1]) {
                    table[i][j] = table[i-array[j-1]][j-1];
                }
            }
        }

        System.out.printf("%10s ", "-");
        for(int i = 0; i <= sum; i++) {
            System.out.printf("%10s ", i);
        }
        System.out.println();
        for(int j = 0; j <= len; j++) {
            System.out.printf("%10s ", j);
            for(int i = 0; i <= sum; i++) {
                System.out.printf("%10s ", table[i][j]);
            }
            System.out.println();
        }

        return table[sum][len];
    }
}

Output:

     -          0          1          2          3          4 
     0       true      false      false      false      false 
     1       true       true      false      false      false 
     2       true       true       true       true      false 
     3       true       true       true       true       true 
     4       true       true       true       true       true

These results look correct. I would interpret some of the values like:

  • table[0][0] is true because {} sums to 0
  • table[1][1] is true because {1} sums to 1
  • table[2][2] is true because {2} sums to 2
  • table[3][2] is true because {1,2} sums to 3
  • table[4][3] is true because {1,3} sums to 4

Upvotes: 1

Related Questions