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

1 answer

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


). 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.



All Articles