Subset sum easy last testcase

#1

Can you please point out the mistake in my code because of which last testcase is giving wrong answer? https://ide.codingblocks.com/s/98288

#2

Hello Urvi.

Your code fails for cases like-
1
4
1 1 0 -2
In your code, there are possibilities that ‘restsum’ doesn’t become 0.

Recurring here is just like knapsack problem, where either you include that element or you move ahead. I see that you’re adding the elements and then including and excluding them. Although, if you’re using this approach, I would suggest that you use hashing and keep things simple.

So here is what we can do. Just iterate over the array one time, and keep on adding and storing elements.

eg- if an array is 1, 4, -2, -2, 5, -4, 3 , then you would have-> 1, 5, 3, 1, 6, 2, 5

Okay, so now you can see that ‘1’ repeats itself, it means that we do have ‘0’ sum in the array, which comes from 4-2-2. That’s it. Try to implement it now.

#3

Sir,
I have implemented the code the way you advised. Even though it is passing for the testcase 1 1 0 -2, but on submitting it still gives wrong answer for second testcase. https://ide.codingblocks.com/s/98425
Please check the code once again. Thanks for help!

#4

Okay so, as you can see there is one more condition here, that is if sum at any position becomes 0, you will have to print yes. You can add this condition in your code.
What I mean is example- 4 , -2 ,-2
Here sum becomes 0 in last position(it can be any position).
So you should add that condition as well.

1 Like