4 Sum - Find a quadruplet with closest sum in C++

The 4 Sum (Find a quadruplet with the closest sum) problem falls under the category of k-Sum problems, which are all related to finding a set of numbers that would sum up to a target or nearly a target. Here, the problem is to determine four numbers (a quadruplet) in each of the arrays where the sum is equal to a certain given number as closely as possible.

To get rid of this issue, useful sorting algorithms such as sorting and two-pointer methodology are normally implemented to cut the time complexity. The first two numbers can be fixed with two loops when the array is sorted, and the other two numbers can be easily fixed using the two-pointer technique, which ultimately makes the complexity of the problem equal to O(n^3). The sorted array can help in the structured search for combinations, and two pointers can be used to control the process depending on the sum of the current quadruplet to search for the value close to the target sum.

The aim is to keep following the sum that comes as close as possible to the aim as we optimizes the sum in a process. Whenever a better quadruplet sum that is closer to the target is obtained, it replaces those found before. As soon as the precise amount equalling the goal is discovered, the search may be stopped because there will not be a superior solution.

This problem is another good practice of optimizing techniques such as sorting and the two-pointer method in addition to forcing to get the solution in the language most efficiently. The problem also shows that when working with larger datasets, appropriate data structures and algorithms should be applied without the risk of weak performance.

Approach-1: Brute-Force Approach

The brute force method can be regarded as straightforward to implement when approaching the 4 Sum problem, but it is also thoroughly inefficient. In this approach, all the possibilities of adding any 4 elements in the input array are checked to find the right combination that is closest to the given target.

Program:

Let us take an example to illustrate the 4 sum problem using the Brute-Force Approach in C++.

Output:

 
Input array: 1 2 -1 -4 -2 3 0 
Target sum: 1
The closest sum to the target 1 is: 1
Input array: 5 3 2 7 8 10 -1 
Target sum: 12
The closest sum to the target 12 is: 12
Input array: 0 0 0 0 
Target sum: 0
The closest sum to the target 0 is: 0
Input array: 1 1 1 1 1 1 
Target sum: 4
The closest sum to the target 4 is: 4
Input array: -1 2 1 -4 3 0 0 -2 
Target sum: 1
The closest sum to the target 1 is: 1   

Explanation:

• In this example, the <vector> header allows the use of the dynamic array type std::type or requires a vector that is essential for working with sets of numbers.
• It offers utility macros, such as INT_MAX, which can be used to set the variable holding the sought item to an extremely large value against which to compare. It contains basic mathematical operations like abs(), which finds an absolute difference.

Function fourSumClosest:

• This Function has two input parameters: nums, a vector of integers, and target, an integer representing the closest sum. The Function returns any quadruplet closest to the target.
• The Function first performs an if statement to determine whether the size of the input vector is less than four. If so, it prints an error message and does not proceed further because it is impossible to form a quadruplet with less than four elements.
• The value assigned to the adjacent sum closestSum is the maximum value of the Int type, INT_MAX, to guarantee that any computed quadruplet sum encountered during the iterations can overwrite this initial value.

Nested Loops:

• The core of the brute-force approach is the four nested loops, which generate all possible combinations of four distinct elements from the input vector.
• The outer Loop selects the first number, and the second Loop selects the second number. After each Loop, the next starts from the index value of the chosen number to avoid repeating the same values and greatly increasing the difference between the lists.
• For each of these combinations, the sum of four chosen randomly selected numbers is computed.

Closest Sum Calculation:

• The current sum of the quadruplet is calculated before this Function stamps it as the closest to the target if it is closer than the former closest sum. This comparison is made by applying the abs() Function to the sums to obtain an absolute difference. If the current sum is closer, it ushers in the closestSum.

Input Display Function:

• This Function prints the vector of input and the target sum when the package is used. It is useful in explaining input data during testing.

Testing Function:

• The C++ file link also shows testFourSumClosest, which includes multiple test cases with array inputs and target sum. For each case, it invokes fourSumClosest and prints the result to facilitate function validation a lot easier.

Complexity Analysis:

Time Complexity

The time complexity of this brute-force method is determined to be O(n^4). This complexity arises from the four nested loops used to iterate through the array:

• Outer Loop: The first Loop runs from the first index to the fourth from the last index of the list.
• Second Loop: The second Loop starts from the next element to the first and moves to the third-last element.
• Third Loop: The third Loop starts right after the second loop index and ends at the second to last element.
• Innermost Loop: The innermost Loop begins just after the third Loop's index and goes all the way up to the last element of the array.

In this regard, since each Loop relies on the other, the number of combinations being evaluated is a polynomial of the size of the input array, specifically a 4th-order polynomial. Therefore, the numbering of iterations increases with the size of the input, which becomes a critical issue for large datasets and considerably degrades the execution speed.

Space Complexity

The space complexity of this approach is constant, O(1). It means that the algorithm takes a constant amount of extra space over and above what is required by the input array. The indices_alloc, current_sum and best_sum variables are used to store the indices, current sum, and best sum, and these variables do not increase with the size of the input. Hence, the algorithm does not need auxiliary data structures that have proportional space complexity with the input size, thus being memory efficient.

Approach-2: Sorting and Two-Pointer Technique

Optimizing and choosing the Two-Pointer method is a good solution for the 4 Sum (Find a quadruplet with the closest sum problem). This method cuts down the time complexity in half compared to the above method using the brute force sorting method and the two-pointer method.

Program:

Let us take an example to illustrate the 4 sum problem using Sorting and Two-Pointer technique in C++.

Output:

 
Input array: 1 2 -1 -4 -2 3 0 
Target sum: 1
The closest sum to the target 1 is: 1
Input array: 5 3 2 7 8 10 -1 
Target sum: 12
The closest sum to the target 12 is: 12
Input array: 0 0 0 0 
Target sum: 0
The closest sum to the target 0 is: 0
Input array: 1 1 1 1 1 1 
Target sum: 4
The closest sum to the target 4 is: 4
Input array: -1 2 1 -4 3 0 0 -2 
Target sum: 1
The closest sum to the target 1 is: 1   

Explanation:

• The main Function, fourSumClosest, takes an Indeed vector, which contains some integers and an Integral target as arguments. First, it verifies whether the size of the array is less than four and if that is the case, it returns an error.
• Following sorting the array for the two-pointer technique, the Function uses two cycles to adjust the first two constituents of the quadruplet. For each fixed pair, two pointers (left and right) are set as the potential candidates for the rest of the two numbers.
• The total of four selected numbers is calculated and then compared with the intended total. Moreover, the displayInput Function prints the input array and target for clarity during testing. The testFourSumClosest Function considers multiple test scenarios, calling fourSumClosest and displaying its result.
• Thus, the method achieves good improvements with the time complexity steadied at O(n^3) better than the brute-force method for larger data sets. Overall, the code structure permits structural testing and highly reliable results can be obtained even under the condition of applicable variations and shades of the scenarios in question. At the same time, the code runs with high lexicality without mixed functionality.

Complexity Analysis:

Time Complexity:

• The technique used in the 4 Sum-Find a quadruplet with the closest sum problem, identified as the Sorting and Two-Pointer Technique, has a time complexity of (O(n3)). This is because sorting the given input array and the nested loops used to identify the pairs are complex.
• Hence, the sorting operation is of order (O(n logn)). The first Loop that makes a pass through the array contributes to the time of order (O N2), and the second Loop also makes a pass through the array contribute to the time of order (O (n2).
• The innermost Loop combined with the two-pointer technique still requires time for the rest of the elements, making the whole Function on average (O(n3)). Consequently, the algorithm fairly reduces the search space, which favors it for large input sizes, outdoing the brute force approach.

Space Complexity:

• The space complexity of this approach is (O(1)), and the algorithm consumes only a constant quantity of extra space. The only other storage used is a few integer variables for indices, sums and the nearest sum discovered. The input array is sorted in place, and no data structures other than the input array itself are used, each of which has a size proportional to the input size. This efficiency in both time and space actually makes the Sorting and Two-Pointer Technique useful in the 4 Sum problem.