Find 4 Elements in An Array that Sum to A Target Value

Problem: Given an array and a target value, find 4 elements in the array that sum to this target value.

Solution: Here introduce an O(n^2) algorithm. Only briefly explain the idea:

• Calculate the sums of all pairs in the array and form a new array. Each element in the new array is a struct that stores the sum and the two elements who make the sum. Sort the array by the sum. The cost is  O(n^2) till now (may need radix sort).
• The problem is converted to find 2 elements in the new array that sum to the target value. The cost for this operation is the length of the new array, which is also O(n^2). So total cost is O(n^2).