# This array finds all combinations of elements that add up to

In an interview, I was asked the following question. Although I answered this using an n-ary tree, I was told that this is not "good enough". So I am curious what is the optimal solution for it.

Input: array of integers: [2, 3, 7] and sum: 10

Output: all combinations of array elements that are summed (e.g. 2 + 2 + 2 + 2 + 2, 2 + 2 + 3 + 3, 3 + 7, etc.)

Thank you

source to share

This problem can be solved with dynamic programming . You have a 2D dp. Let's say you are doing dp on an array named `mem`

. mem [i] [j] will store the number of ways to reach the sum `i`

with the elements of the indices `j, j + 1... n`

(here `n`

- the size of the array).

You have the following relationship `mem[i][j] = mem[i][j+1] + mem[i - a[j]][j+1]`

(of course, you need to check if less `i`

`a[j]`

). And now you can find the number of ways to reach the sum `S`

by getting the value `mem[S][j]`

. restoring solutions is not very difficult if you have an array. I suggest you try doing it yourself and write a comment if you can't figure it out.

source to share