Getting wrong answer

#1

HI ,
This is a doubt regarding the sum it up question . I have approached this question in a way quite similar to knapsack problem but I’m getting wrong answers It will be great if someone can tell me what is going wrong with the code

#2

Hey @imsharan0105 knapsack won’t work in this case, check for input:
15
57 79 16 3 83 70 78 14 5 8 36 51 47 93 72
86
Expected output is:
3 5 8 70
3 5 78
3 36 47
3 83
5 8 16 57
5 14 16 51
8 78
14 72
16 70
Solve using this technique

your code logic is partially correct.
this is the approach :

  • Sort the array(non-decreasing).
  • First remove all the duplicates from array.
  • Then use recursion and backtracking to solve the problem.
      1. If at any time sub-problem sum == 0 then add that array to the result (vector of vectors).
      1. Else if sum if negative then ignore that sub-problem.
      1. Else insert the present array in that index to the current vector and call the function with sum = sum-ar[index] and index = index, then pop that element from current index (backtrack) and call the function with sum = sum and index = index+1
        Code for reference
#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

1 Like
#4

Hi , you have sorted the array only to ensure that we do not get the same element again right?

#5

Right …

#6

Thanks , it is a really nice approach by you I modfied my code and pushed all unique combinations into vector<vector>. I first sorted all elements in the current vector and also checked that this vector is not already present in vector<vector> . If not then i pushed it into the vector else I simply returned