使用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