通过DP的子集和

Question

在http://comproguide.blogspot.in/2013/10/subset-sum-problem.html
然而，我通过一个小练习列举了这个算法，以在{1,2,3,4}中找到和为4的子集。

我注意到单元格｛1，1｝，｛2，2｝返回一个false。

我把逻辑理解错了吗
或者算法不认为集合是其自身的子集？

我本来希望｛1，1｝返回一个true，因为1本身加起来。

Answer 1

｛1｝应该算作和为1的子集。我在程序中添加了一些输出以显示表格：

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];
    }
}

输出：

     -          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 

这些结果看起来是正确的。我会解释一些值，比如：

• 表[0][0]为true，因为｛｝和为0
• 表[1][1]为真，因为｛1｝和为1
• 表[2][2]为真，因为｛2｝和为2
• 表[3][2]为真，因为{1,2}和为3
• 表[4][3]为真，因为{1,3}和为4

Answer 2

我是这篇文章的作者。@fgb显示的输出看起来是正确的。我认为代码没有任何问题。我的解释有什么不对吗？