問(wèn)題描述

我一直在學(xué)習(xí)動(dòng)態(tài)編程，我想通過(guò)打印所有加起來(lái)為一個(gè)數(shù)字的子集來(lái)進(jìn)一步解決經(jīng)典的子集求和問(wèn)題.我該怎么做呢?截至目前，我知道如何根據(jù)是否有一個(gè)子集相加來(lái)打印真假

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

如果可能，我想返回一個(gè)包含所有子集的數(shù)組.

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

推薦答案

這個(gè)問(wèn)題比原來(lái)的問(wèn)題更難.

This problem is harder than the original one.

對(duì)于您設(shè)置為 true 的每個(gè) table[i][j]，您必須標(biāo)記其所有 predecessors 即所有 table[i1][j1]=true，因此您將 table[i][j] 標(biāo)記為 true.通過(guò)這種方式，您可以構(gòu)建一種圖結(jié)構(gòu).該圖的頂點(diǎn)是對(duì)(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).

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

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.

這篇關(guān)于子集和找到所有加起來(lái)為一個(gè)數(shù)字的子集的文章就介紹到這了，希望我們推薦的答案對(duì)大家有所幫助，也希望大家多多支持html5模板網(wǎng)！