4 Sum
WHAT IT SAYS
Find all unique quadruplets in an array that sum to a given target, with no duplicate quadruplets in the output.
WHAT IT'S REALLY ASKING
"Strip one number off the front and what is left is literally 3Sum with a shifted target. Strip another and it is 2Sum on a sorted array — which closes in a single linear squeeze. So there is no new problem here, only a question: how deep do you nest before the two fingers take over?"
Four nested loops and a set
O(n^4) time, O(number of quadruplets) spaceEnumerate every quadruple of indices, keep the ones hitting the target, sort each survivor and dump it into a set to kill the duplicates.
WHERE THE WORK IS WASTED — The fourth loop is a linear search for a number that is already fully determined — once a, b and c are chosen, the last one has to be target - a - b - c. And the duplicate problem is exponential in the wrong direction: an unordered quadruplet has 24 index orderings, so you discover each answer up to 24 times and then pay memory to throw 23 of them away. You are generating garbage deliberately and then hiring a set to clean it up.
kSum is (k-1)Sum with a new target.
Sort the array. Now fix the smallest member of a quadruplet, a[i]. Every quadruplet whose smallest-index member is i corresponds one-to-one with a TRIPLET in the suffix after i that sums to target - a[i]. Nothing is lost: any quadruplet has exactly one first element under the index ordering i < j < k < l, so it is counted at exactly one i, never zero and never twice. The permutation-duplication that the brute force manufactured is not filtered out afterwards — it is prevented from existing. Apply the same reduction again. Fix a[j] and the triplet problem becomes a PAIR problem in the remaining suffix, with target minus two known numbers. So the recursion is: kSum on n elements = n copies of (k-1)Sum, until you bottom out. And the base case is the whole point. 2Sum on a sorted window is not another loop — it is a linear squeeze, because a[l] + a[r] is at once the largest sum a[l] can reach and the smallest a[r] can reach. Too small and a[l] is hopeless against everything remaining; too big and a[r] is. Each comparison retires an element, so the base case costs O(n) and the total is O(n^(k-1)). Duplicates die at every level with the same one-line rule: within a level, skip a value equal to the previous one you fixed. Sorting put equal values next to each other, so 'have I already used this as my first element?' is a glance at the neighbour, not a lookup in a table of everything you have ever emitted.
Sort, fix two, squeeze the rest
O(n^3) time, O(1) extra space beyond the sort and outputSort. Loop i, skipping i where a[i] equals a[i-1]. Loop j from i+1, skipping j where a[j] equals a[j-1]. Then two pointers on the suffix, hunting for target - a[i] - a[j]: too small, l++; too big, r--; exact, record and slide both pointers past their equal runs. Do the arithmetic in 64-bit — four ints can overflow a 32-bit sum, and that bug has nothing to do with the algorithm and everything to do with failing the test case.
Peel to the Base Case
YOU'LL SEE IT AGAIN WHEN
- The problem is the k-way version of something you can already solve for k-1, with the target simply shifting by the value you fixed.
- Order among the chosen elements is irrelevant, so you can impose i < j < k < l and kill every permutation-duplicate by construction rather than by filtering.
- Once k-1 values are fixed the final one is determined, so the innermost step should be a lookup or a squeeze — never a search.