我一直在学习动态规划,我想进一步解决经典的子集求和问题,打印出所有加起来等于一个数的子集。我到底该怎么做呢?截至目前,我知道如何根据是否存在相加的子集来打印 true 或 false
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];
}
如果可能,我想返回所有子集的数组。
最佳答案
这道题比原题难。
对于每个设置为 true
的 table[i][j]
,您必须标记其所有 predecessors 即所有 table[i1][j1]=true
,因此您将 table[i][j]
标记为 true。这样你就构建了一种图形结构。
该图的顶点是一对 (i,j)
。
然后当你想打印答案时,你必须从 (i,j)
追溯到所有可能的 (i1,j1)
等等向后.为此,仅仅一个数组是不够的,您需要额外的/辅助数据结构。
关于java - subset sum 找到加起来等于一个数的所有子集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34274701/