問題描述

我一直在學習動態編程，我想通過打印所有加起來為一個數字的子集來進一步解決經典的子集求和問題.我該怎么做呢?截至目前，我知道如何根據是否有一個子集相加來打印真假

I have been learning dynamic programming, and I want to take the classic subset sum problem a little further by printing out all the subsets which add up to a number. How exactly would I go about doing this? As of now, I know how to print true or false based on whether there is a subset that adds up to it

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

如果可能，我想返回一個包含所有子集的數組.

if possible, I'd like to return an array of all of the subsets.

推薦答案

這個問題比原來的問題更難.

This problem is harder than the original one.

對于您設置為 true 的每個 table[i][j]，您必須標記其所有 predecessors 即所有 table[i1][j1]=true，因此您將 table[i][j] 標記為 true.通過這種方式，您可以構建一種圖結構.該圖的頂點是對(i,j).

For each table[i][j] which you set to true, you have to mark all its predecessors i.e. all the table[i1][j1]=true, due to which you marked table[i][j] as true. This way you build a kind of graph structure. The vertices of this graph are couples (i,j).

然后當你想打印答案時，你必須從 (i,j) 回溯到所有可能的 (i1,j1) 等等.為此，僅一個數組是不夠的，您需要額外的/輔助數據結構.

Then when you want to print the answer, you have to trace back from (i,j) to all possible (i1,j1) and so on going backwards. For this, just an array won't be enough, you'll need additional/helper data structures.

這篇關于子集和找到所有加起來為一個數字的子集的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！