Quadruplets Summing to Target

You are given an array of n integers and an integer target. Find all unique quadruplets of positions whose values sum exactly to target. A quadruplet is unique by its multiset of values: the same combination of four numbers must not be reported more than once even if it can be formed from different positions.

Input: The first line contains the integer n. The second line contains n space-separated integers. The third line contains the integer target. Output: Print each unique quadruplet on its own line as four space-separated integers in non-decreasing order (a <= b <= c <= d). Quadruplets must be printed in non-decreasing order by first element, then second, then third, then fourth. If no such quadruplet exists, print nothing.

4 <= n <= 300 -10^5 <= arr[i] <= 10^5 -10^5 <= target <= 10^5

This caps off the k-sum FAMILY of problems (two-sum via hash map or sorted two-pointer, three-sum via fix-one-plus-two-pointer, four-sum via fix-two-plus-two-pointer) - recognizing this whole family as ONE extensible pattern, rather than four separate techniques, is one of the most valuable pattern-recognition skills in this entire category.

Find every unique quadruplet of values in an array that sums to a target, extending the triplet-sum technique by one more level. Brute force: Check every possible quadruplet of positions directly with four nested loops - this costs O(n⁴), far too slow even for moderately sized arrays. Optimised: Extending the three-sum technique by one more level of nested fixing (fix two elements instead of one) and using two pointers for the remaining pair reduces the search from O(n⁴) to O(n³) - sorting still enables both the two-pointer scan and the adjacent-duplicate-skipping needed at every one of the four positions.

1. Sort the array first, then fix the FIRST TWO elements of the quadruplet with NESTED LOOPS, skipping duplicate values at each fixed position to avoid repeat quadruplets. 2. For the REMAINING two positions, use TWO POINTERS moving inward across the rest of the sorted array, just like in the three-sum problem. 3. After finding a valid quadruplet, advance past any further occurrences of the SAME VALUES at both the left and right pointers before continuing the search.

Time: O(n³) - sorting costs O(n log n), and for each of the O(n²) pairs of fixed first-two-elements, a two-pointer scan costs O(n). Space: O(1) extra space beyond the sort itself.

Handle the smallest n = 4 (at most one possible quadruplet) and arrays with many repeated values where duplicate quadruplets must be suppressed; sort first, fix two elements, and use two pointers on the remainder with 64-bit sums to stay within O(n^3) at n = 300.

Be ready to explain this as a direct generalization of three-sum - the same 'fix elements, two-pointer the rest' skeleton, just with one MORE level of fixing, and generalizing further to k-sum follows the exact same recursive pattern.