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)等等後退。爲此，只需一個數組是不夠的，你需要額外的/輔助數據結構。