79. Find Four Elements That Sum to a Given Value

Given an array of n integers and a target value, print 'Yes' if there exist four elements (at four distinct indices) whose sum equals the target, otherwise print 'No'.

Input: The first line contains an integer n. The second line contains n space-separated integers. The third line contains the target value. Output: Print 'Yes' if four elements at four distinct indices sum to the target, otherwise print 'No'.

1 <= n <= 500

Watch out for reusing the SAME element twice across your two chosen pairs - you must ensure all four indices are genuinely distinct, not just that the two pair-sums add up correctly.

You're given a pile of numbers and a target total. You need to find out if you can pick exactly FOUR of them (from four different positions) that add up to that exact target - like trying to find four price tags in a store that together cost exactly ₹91. Brute force: Try every possible combination of four distinct indices directly (four nested loops), computing their sum and checking against the target - this costs O(n⁴), which becomes far too slow once n grows past a few hundred. Optimised: Reduce '4 numbers summing to a target' into '2 PAIR-SUMS summing to a target' - precompute every pair's sum once (O(n²) pairs), store them in a hash map keyed by sum (with their index pairs), then for each pair-sum, look up its complement (target minus that sum) in the map in O(1). This turns an O(n⁴) brute force into roughly O(n²), a massive improvement.

Use four nested loops over all combinations of four distinct indices i < j < k < l and check whether the four corresponding values sum to the target, stopping as soon as one is found. This checks every possible quadruple directly, guaranteeing correctness, but the number of quadruples to examine grows with the fourth power of the array size. Time: O(n^4) Space: O(1)

Precompute every pairwise sum a[i] + a[j] for i < j and, for each sum value, store the list of index pairs that achieve it in a hash map. Then, for every other pair (k, l) with k < l, look up target - (a[k] + a[l]) in the map, and if a stored pair exists whose two indices are both different from k and l, the four indices together answer the question. Since only existence is required (not the actual quadruple), this only needs to check disjointness against the small list of pairs stored under one hash bucket rather than doing a full nested scan, cutting the search from cubic down to roughly quadratic time at the cost of quadratic space to store all pairwise sums. Time: O(n^2) average Space: O(n^2)

Sort the array first, then fix the first two indices i and j with a double loop, and for each fixed pair use a two-pointer scan over the remaining subarray (one pointer from just after j, one from the end) to look for two more elements summing to target - a[i] - a[j], moving the pointers inward based on whether the current sum is too small or too large. Sorting lets the innermost two-index search be resolved in linear time instead of nested loops, cutting one full order of complexity off the brute force approach. Time: O(n^3) Space: O(1) extra (O(n log n) for sort)

1. First, generate every possible PAIR of elements and compute each pair's sum, remembering which two indices made that sum. 2. You now effectively need two of these pair-sums to add up to the target (since two pairs = four elements total). 3. For each pair-sum, check if (target - that pair-sum) also exists as another pair-sum, using indices that don't overlap with the first pair. 4. If you find such a match, four elements exist that sum to the target - answer Yes.

Time: Roughly 'n squared' - computing all pairs takes n² work, and each lookup in the hash map is instant, so the overall cost scales with the number of pairs, not the number of four-element combinations. Space: O(n²) in the worst case, since you're storing every pair's sum (and there are roughly n²/2 pairs) in a hash map.

n < 4 (no valid quadruple exists, answer No), n up to 500 to confirm the pair-sum hashing approach performs well, and duplicate values that could otherwise cause an index to be reused.

This is the classic 'reduce k-sum to (k/2)-sum using a hash map' technique - the exact same idea extends to 3-sum, 4-sum, and beyond, and interviewers often ask you to generalize it after solving the 4-element case.