java - 配列内の完全な合計を計算する関数を記述しますか？

Question

完全な合計とは、合計が指定された数に等しい配列の2つ以上の要素の合計です。見つからない場合は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完全ですが、比較的小さい整数の場合は、疑似多項式時間で動的計画法を使用して解決できます。

小さな配列で実行可能な、おそらくより単純な代替手段はブルートフォースです。可能なすべてのサブセットを検索し、合計と一致するかどうかを確認します。

これらのガイドラインは、問題のプログラミングを開始し、自分で問題（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] ) ;
}