子集和问题：查找所有加起来等于一个数字的子集

Question

子集和问题：查找所有加起来等于一个数字的子集

javasumdynamic-programmingsubsetsubset-sum

4

我一直在学习动态规划，我想通过打印出所有加起来等于某个数字的子集来进一步了解经典的子集和问题。我应该怎么做呢？目前为止，我只知道如何根据是否存在一个加起来等于这个数字的子集来打印真或假。

    public static boolean hasSum(int [] array, int sum)
{
    int len = array.length;
    boolean[][] table = new boolean[sum+1][len+1];

    int i;

    for( i = 0; i <= len; i++ )
        table[0][i] = true;

    for( i = 1; i <= sum; i++ )
        table[i][0] = false;

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

    return table[sum][len];
}

如果可能的话，我想返回所有子集的数组。

- seanscal

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- peter.petrov · Accepted Answer

这个问题比原来的问题更难。对于每个你设置为true的table[i][j]，你必须标记它的所有前置节点，即所有使table[i][j]被标记为true的table[i1][j1]=true。这样，您就建立了一种图形结构。这个图的顶点是(i,j)对。然后，当您想要打印答案时，您必须从(i,j)向后跟踪到所有可能的(i1,j1)等，以此类推。为此，仅使用数组是不够的，您需要额外/辅助数据结构。