C++で許可されている繰り返しの配列要素を使用してNに合計する方法

この問題では、整数の配列と数値Nが与えられます。私たちのタスクは、配列の要素を追加することによってNを生成できる方法の総数を数えることです。すべての組み合わせと繰り返しが許可されます。

問題を理解するために例を見てみましょう

入力

arr = {1, 3, 5} N = 6

出力

8

説明

方法は-

5+1, 1+5, 3+3, 3+1+1+1, 1+3+1+1, 1+1+3+1, 1+1+1+3, 1+1+1+1+1+1

この問題を解決するには、すべてのタイプの組み合わせが異なる方法で処理されるため、異なるアプローチを使用する必要があります。そのため、数が配列の4つの要素の合計である場合、4つの異なる方法が考慮されます（例を参照）。このような問題を解決するには、動的計画法を使用する必要があります。以下のプログラムで実装を示します。

例

#include <iostream>
#include <cstring>
using namespace std;
int arraySumWays(int array[], int size, int N){
   int count[N + 1];
   memset(count, 0, sizeof(count));
   count[0] = 1;
   for (int i = 1; i <= N; i++)
      for (int j = 0; j < size; j++)
         if (i >= array[j])
            count[i] += count[i - array[j]];
   return count[N];
}
int main() {
   int array[] = {1, 5, 6};
   int size = sizeof(array) / sizeof(array[0]);
   int N = 7;
   cout<<"Total number of ways inwhich "<<N<<" can be generated using sum of elements of array is "      <<arraySumWays(array, size, N);
   return 0;
}

出力

Total number of ways inwhich 7 can be generated using sum of elements of array is 6