educative.io

Educative

Why should searchPair look for target sum only in index i+1 and above?

In this line: searchPair(arr, -arr[i], i+1, triplets)
why is there i+1. Why can’t the required targetSum be found in the entire array.

I think it somehow avoids duplicates but can’t grasp why it does so.

Can someone help me understand?

Thank you.

The reason is:
X + Y + Z = target.
arr = {-5, -2, -1, 2, 3 } We select Z one by one, for eg. Z = -5 and then find all possible pairs X + Y. In the next loop we select -2 and all possible pairs X + Y. At this point if you let one of X or Y be -5, you will stumble upon the same pair you already got when Z was -5, creating a duplicate. So, only let X Y be elements after i+1.

Also, I was wondering why both left++ and right++ when we find the pairSum==targetSum. The reason being: X(left) + Y(right) formed targetSum, now there is no other number with X that can form targetSum. Similarly, there is no number with Y that can form targetSum, So, we move on on both sides.