子集总和找到所有加起来为数字的子集 [英] subset sum find all subsets that add up to a number

问题描述

我一直在学习动态编程，我想通过打印出所有加起来等于数字的子集来进一步解决经典的子集和问题。我将如何去做呢？到目前为止，我知道如何根据是否有子集来打印true或false

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的表[i] [j] ，您必须标记其所有前辈，即所有表[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.

这篇关于子集总和找到所有加起来为数字的子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！