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.

  • 1
    $\begingroup$ What are your approaches? $\endgroup$ – SiluPanda May 31 '19 at 16:24
  • $\begingroup$ i am not able to classify the problem $\endgroup$ – soumya sambit Kunda May 31 '19 at 17:16
  • $\begingroup$ have you tried to solve it by brute-force? $\endgroup$ – SiluPanda May 31 '19 at 17:53
  • 1
    $\begingroup$ 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. $\endgroup$ – Nathaniel May 31 '19 at 19:00
  • $\begingroup$ 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? $\endgroup$ – gnasher729 May 31 '19 at 22:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.