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