If I had four arrays with the same size, how do I determine the number of ways to choose one element from each array such that the four elements have the same sum?

For example, there are 81 ways to choose choose an element from each array with a sum of 4.

A. 1 1 1 
B. 1 1 1 
C. 1 1 1 
D. 1 1 1 

I am not sure how to do this without some sort of brute forcing.

CodePudding user response：

The idea

1. Number of ways to get sum k from 1 array = number of occurences of k in the array.
2. Number of ways to get sum k from 2 arrays = sum(count(k-x) for each element x in array 2), where count(y) is number of ways of getting sum y from the first array. If you memoize the results from point #1, getting count(y) can be done in O(1).
3. Number of ways to get sum k from 3 arrays = sum(count(k-x) for each element x in array 3), where count(y) is number of ways of getting sum y from the first two arrays. Again, if you memoize the results from point #2, getting count(y) can be done in O(1).

You should get the concept by now; number of ways to get sum k from n arrays = sum(count(k-x) for each element x in the nth array), where count(y) is number of ways of getting sum y from the first n-1 arrays.

Dynamic programming

You need to build a memoization table which basically tells you the number of ways of getting sum x from the first y arrays. If you have this table for the first n-1 arrays, you can calculate all sums including the n-th array efficiently and update the table.