3

I've been asked the following question in an interview. Although I've answered it using an n-ary tree, I've been told it wasn't "good enough". So, I'm curious, what's the optimal solution for it.

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

Output: all combinations of array elements that add up to sum (e.g. 2+2+2+2+2, 2+2+3+3, 3+7, etc.)

Thanks, T

MrTibs
  • 161
  • 1
  • 12
  • Hint: Every combination that adds up to 10 must consist of either a combination that adds up to 8, to which 2 can then be added; a combination that adds up to 7, to which 3 can then be added; or a combination that adds up to 3, to which 7 can then be added. – j_random_hacker Oct 02 '14 at 08:48
  • Here you might find a good approach http://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum that might suits your case. – Christos Oct 02 '14 at 09:12

1 Answers1

0

This problem can be solved using dynamic programming. You have two dimensional dp. Lets say you do the dp in an array called mem. mem[i][j] will store the number of ways you can achieve sum i with the elements of indexes j, j + 1... n(here n is the size of the array).

You have the following relation mem[i][j] = mem[i][j+1] + mem[i - a[j]][j+1](of course you need to check if i is not less than a[j]). And now you can find the number of ways in which you can achieve sum S by getting the value of mem[S][j]. reconstructing the solutions is not very hard once you have the array. I suggest you try to do that on your own and write a comment if you can't figure it out.

Ivaylo Strandjev
  • 69,226
  • 18
  • 123
  • 176
  • From the OP's example, each element can be used more than once (i.e. it's not the usual Subset Sum problem), so you need to also add `mem[i - 2 * a[j]][j+1]`, `mem[i - 3 * a[j][j+1]` etc. to `mem[i][j]`. – j_random_hacker Oct 02 '14 at 16:48