# Given an array of sum and an array how can to find if all the sums are possible using distinct elements of array?

example:

if we have array of int as 1 2 3 and sum array is given 3,3 we can form this sum as {1,2} and {3} if the sum array is 5 3 we can not create the sum array, we can for {2,3} but not enough items to form the sum 3.

Can someone help me to understand which algorithm can be used to solve the problem.

• What are your approaches? – SiluPanda May 31 '19 at 16:24
• i am not able to classify the problem – soumya sambit Kunda May 31 '19 at 17:16
• have you tried to solve it by brute-force? – SiluPanda May 31 '19 at 17:53
• This looks like a generalization of the subset sum problem (en.wikipedia.org/wiki/Subset_sum_problem), which $\textsf{NP}$-complete (with one sum to the target and the others to 0). I doubt you will find a good algorithm for it. – Nathaniel May 31 '19 at 19:00
• If you want to count the solutions, you need to define how you count it. In your first example, [1+2, 3] is one solution, Is [3, 1+2] another one? – gnasher729 May 31 '19 at 22:01