java - 编写一个计算数组中完美和的函数？

Question

完美和是两个或多个数组元素的总和，其和等于给定数。如果没有找到返回 999。

我的方法签名是：

public static int persfectSum(int arr[], int input)

例如：

arr={2,3,5,6,8,10}
input = 10;

5+2+3= 10
2+8 = 10
So, the output is 2;

Answer 1

它是子集和问题的一种变体——对子集的大小有额外的限制（大于 1）。

问题是NP-Complete，但是对于相对较小的整数，可以使用伪多项式时间内的动态规划来解决。

对于小型数组可行的一种可能更简单的替代方案是蛮力 - 只需搜索所有可能的子集，并验证每个子集是否与总和匹配。

我相信这些指南足以让您开始编写问题并自行解决问题（HW？）。

祝你好运。

Answer 2

int PerfectSums(int n, int a[], int sum)
{

    int dp[n + 1][sum + 1] ;
    dp[0][0] = 1;

    for (int i = 1; i <= sum; i++)
        dp[0][i] = 0;

    for (int i = 1; i <= n; i++)
        dp[i][0] = 1;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= sum; j++)
        {

            if (a[i - 1] > j)
                dp[i][j] = dp[i - 1][j];

            else
            {
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - a[i - 1]];
            }
        }
    }

    return (dp[n][sum] == 0 ? 999 : dp[n][sum] ) ;
}