Target Sum Triplets

#1

I have solved this by O(N^3) time complexity. Is there any other optimized method for this that can take less than N^3?

#2

hello @rahul_bansal

yeah we have O(N^2) approach for this problem ->

  1. Sort the given array.
  2. Loop over the array and fix the first element of the possible triplet, arr[i].
  3. Then fix two pointers, one at i + 1 and the other at n – 1. And look at the sum,
  4. If the sum is smaller than the required sum, increment the first pointer.
  5. Else, If the sum is bigger, Decrease the end pointer to reduce the sum.
  6. Else, if the sum of elements at two-pointer is equal to given sum then print the triplet and decrment end pointer and increment first pointer
1 Like
#3

I have solved this earlier by this code: https://ide.codingblocks.com/s/478922

Can you please tell me what is the error in this code?

#4

it will not print all pairs.

1 Like
#5

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.