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

问题描述

我一直在学习动态编程，我想通过打印所有加起来为一个数字的子集来进一步解决经典的子集求和问题.我该怎么做呢?截至目前，我知道如何根据是否有一个子集相加来打印真假

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.

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