Find Four Elements That Sums To A Given Value

1. We will check the sum of every possible combination of four indices using 4 nested loops.
2. If the sum is equal to the ‘target’ that means we found our quadruple. So, we return true in this case else we simply return false.

1. We first need to sort the array and fix the two indices ‘i’ and ‘j’ for our first element and second element respectively, where 0 <= i < N-3 , i+1 <= j < N-2.
2. The idea here is: For all pairs of the first and second element, we find the possible indices for the third and fourth element in a single loop using two pointer technique.
3. Let us understand how two-pointers will help us, we put two-pointers at the starting and the ending of the remaining suffix [j+1, N-1]. Suppose left = j+1, and right = N-1 so our current sum will be arr[i] + arr[j] + arr[left] + arr[right] now if this sum is equal to ‘target’ that means we found one correct quadruple so we return true in that case.
   • If the sum is less than ‘target’ that means we need to increase our sum so make it equal to the required sum ‘target’. You can observe that arr[i] + arr[j] is constant and we can only change arr[left] or arr[right].
   • As we already sort the array this implies arr[left] < = arr[right] and arr[right] is already having a greater value so we can’t increase arr[right] further. In this case, we move forward through the ‘left’ pointer because arr[left+1] >= arr[left] to match up with the required sum.
   • Else if the sum is greater than ‘target’ that means we need to decrease our current sum so in this case, we move backward through the ‘right’ pointer because arr[right-1] <= arr[right] to match up with the required sum.
4. At last, if we can not find any valid quadruple then we return false in that case.

1. We will create a temporary array temp[] to store the sum of all possible pairs.
2. Now we sort this temp[] array. As each element of temp[] contains the sum of two elements so the problem reduces to finding the two pairs in the temp[] such that their sum is equal to ‘target’.
3. We can use two pointer technique to check whether there exist two pairs in the temp[] array that gives the sum = ‘target’. Similar to the above approach we will put the first pointer (left) at the starting and the second pointer (right) at end of temp[] array.

Now if temp[left] + temp[right] = target that means we found a pair but we also need to check whether these two elements of temp have an element of arr[] in common or not for ensuring that the elements we pick have distinct indexes.

1. To check the distinct indexes we need to declare the type of temp as a structure in which we can store sum and both indexes as separate fields.
2. We just access both indexes of temp[left] and temp[right] and if they have any common index then this can not be a valid pair.
   • If temp[left] + temp[right] < target so similar to the above approach we will move our ‘left’ pointer to right else we move the ‘right’ pointer to the left.

1. We will store the sum of all possible pairs in a hashmap having sum as its key and a pair of indexes as its value.
2. To find pair sum we run 2 nested loops for choosing the first and the second element of quadruple let us say their sum is arr[i] + arr[j] then we try to find the remaining sum ( target - arr[i] - arr[j] ) from the hashmap.
3. If the hashmap contains a key = target - arr[i] - arr[j] that means we have a pair present in the hashmap such that their sum is ‘target’.
4. In the next step similar to the above approach we must check whether these two pairs of elements have an element of arr[] in common or not for ensuring that the element is not considered more than once.
5. For doing so we simply extract the indexes of other pairs ( target - arr[i] - arr[j] ) from the hashmap and check if the two indexes are different from ‘i’  and ‘j’ or not.