subset sum找到加起来的数字的所有子集

Question

我一直在学习动态规划，并且我想通过打印出加起来的所有子集来进一步考虑经典的子集求和问题。我该如何去做这件事？截至目前，我知道如何根据打印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]; 
} 

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

Answer 1

这个问题比原来的难。

对于您设置为true每个table[i][j]，你必须标记所有前辈即所有table[i1][j1]=true，由于您标记table[i][j]为真。这样你就可以建立一种图形结构。 该图的顶点是夫妇(i,j)。

然后，当你想打印答案时，你必须从(i,j)追溯到所有可能的(i1,j1)等等后退。为此，只需一个数组是不够的，你需要额外的/辅助数据结构。