Quadruple Sum to Target
Mahabharata — The Four Pillars — Balancing the Sacred Yagna Fire
चतुर्भिः स्तम्भैः यज्ञवेदी समर्थ्यते। समत्वं लक्ष्यसंप्राप्त्यै आवश्यकं सदा भवेत्॥
*The sacrificial altar is supported by four pillars. Equilibrium toward the target is always essential.*
The Story
The great yagna at Indraprastha required a fire altar of perfect balance. Four pillars of gold, silver, copper, and iron would support the sacred platform, and their combined weight must equal exactly 108 bharas—the sacred number.
Yudhishthira summoned the royal architect. "We have many metal ingots of varying weights. Find all unique combinations of four ingots that sum to 108. The combinations must be distinct—no repeated selections."
The available ingots weighed: [1, 0, -1, 0, -2, 2]
Bhima, ever direct, suggested brute force: "I'll try every combination of four ingots! With six ingots, that's only 15 combinations."
"For six ingots, yes," the architect replied. "But the treasury holds thousands of ingots for future yagnas. We need an efficient method that scales."
Arjuna, having learned from Krishna, recognized the pattern. "This is the triplet problem extended by one dimension. For triplets summing to a target, we fix one element and reduce to pair-sum. For quadruplets, we fix two elements and reduce to pair-sum."
He sorted the ingots: [-2, -1, 0, 0, 1, 2] and began:
**Fix first two elements: -2 (i=0) and -1 (j=1)** Target for the remaining pair: 108 - (-2) - (-1) = 108 + 3 = 111 Search for pairs in [0, 0, 1, 2] summing to 111.
Using two pointers: left=2 (value 0), right=5 (value 2). 0 + 2 = 2 << 111. No matter how we move pointers, we can't reach 111. No valid quadruplets with this fixed pair.
**Actually, let's use target = 0 for demonstration:**
New setup: Find quadruplets summing to 0.
**Fix i=0 (-2) and j=1 (-1)** Target for pair: 0 - (-2) - (-1) = 3 Two pointers on [0, 0, 1, 2]: seeking sum = 3. - left=2 (0), right=5 (2): 0+2=2 < 3 → left++ - left=3 (0), right=5 (2): 0+2=2 < 3 → left++ - left=4 (1), right=5 (2): 1+2=3 = 3 ✓ - Found: [-2, -1, 1, 2] - Skip duplicates, advance pointers. left=5, right=4. Done with this fixed pair.
**Fix i=0 (-2) and j=2 (0)** Target for pair: 0 - (-2) - 0 = 2 Two pointers on [0, 1, 2]: seeking sum = 2. - left=3 (0), right=5 (2): 0+2=2 = 2 ✓ - Found: [-2, 0, 0, 2] - Skip duplicate left values (another 0 at position 3? No, we're past it). Move pointers. - left=4 (1), right=4. Done.
**Fix i=0 (-2) and j=3 (0)** But wait—j=3 has the same value as j=2. Skip to avoid duplicate quadruplets!
**Fix i=0 (-2) and j=4 (1)** Target for pair: 0 - (-2) - 1 = 1 Two pointers on [2]: only one element, can't form pair. Done.
**Fix i=1 (-1) and j=2 (0)** Target for pair: 0 - (-1) - 0 = 1 Two pointers on [0, 1, 2]: seeking sum = 1. - left=3 (0), right=5 (2): 0+2=2 > 1 → right-- - left=3 (0), right=4 (1): 0+1=1 = 1 ✓ - Found: [-1, 0, 0, 1]
The process continued, tracking unique quadruplets: - [-2, -1, 1, 2] - [-2, 0, 0, 2] - [-1, 0, 0, 1]
"Three unique quadruplets summing to 0," Arjuna concluded. "The pattern is clear: nest two loops to fix the first two elements, then use two pointers for the remaining pair. Skip duplicates at each level."
The architect was impressed. "O(n³) instead of O(n⁴). For a thousand ingots, that's a billion operations instead of a trillion."
"And the technique extends," Arjuna added. "For k-sum problems: fix k-2 elements with nested loops, use two pointers for the final pair. The complexity is O(n^(k-1))."
The yagna altar was built with perfect balance. And in the archives of algorithmic wisdom, the quadruple sum technique was recorded: reduce by fixing elements, one dimension at a time, until a pair problem remains.
This is the Two Pointer technique for finding quadruplets that sum to a target.
Bhima's First Instinct
Use four nested loops to check every possible quadruplet. O(n⁴) time complexity.
public List<List<Integer>> fourSumBruteForce(int[] nums, int target) {
Set<List<Integer>> resultSet = new HashSet<>();
int n = nums.length;
Arrays.sort(nums); // For consistent ordering in results
for (int i = 0; i < n - 3; i++) {
for (int j = i + 1; j < n - 2; j++) {
for (int k = j + 1; k < n - 1; k++) {
for (int l = k + 1; l < n; l++) {
long sum = (long)nums[i] + nums[j] + nums[k] + nums[l];
if (sum == target) {
resultSet.add(Arrays.asList(
nums[i], nums[j], nums[k], nums[l]
));
}
}
}
}
}
return new ArrayList<>(resultSet);
}Arjuna's Wisdom
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
int n = nums.length;
for (int i = 0; i < n - 3; i++) {
// Skip duplicate i values
if (i > 0 && nums[i] == nums[i - 1]) continue;
// Early termination: if smallest 4 elements exceed target
if ((long)nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target) break;
// Skip: if nums[i] + three largest is still less than target
if ((long)nums[i] + nums[n-1] + nums[n-2] + nums[n-3] < target) continue;
for (int j = i + 1; j < n - 2; j++) {
// Skip duplicate j values
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
// Early termination for j
if ((long)nums[i] + nums[j] + nums[j+1] + nums[j+2] > target) break;
if ((long)nums[i] + nums[j] + nums[n-1] + nums[n-2] < target) continue;
// Two pointers for remaining pair
int left = j + 1;
int right = n - 1;
long pairTarget = (long)target - nums[i] - nums[j];
while (left < right) {
long sum = nums[left] + nums[right];
if (sum == pairTarget) {
result.add(Arrays.asList(
nums[i], nums[j], nums[left], nums[right]
));
// Skip duplicates
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < pairTarget) {
left++;
} else {
right--;
}
}
}
}
return result;
}
// Test with ingot weights
public static void main(String[] args) {
int[] ingots = {1, 0, -1, 0, -2, 2};
int target = 0;
List<List<Integer>> quads = new Solution().fourSum(ingots, target);
System.out.println(quads);
// Output: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
}Step-by-Step Walkthrough
Array: [1, 0, -1, 0, -2, 2], Target: 0
Sorted: [-2, -1, 0, 0, 1, 2]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=0 (-2), j=1 (-1), pairTarget=3
[-2, -1, | 0, 0, 1, 2]
i j L R
L=2 (0), R=5 (2): 0+2=2 < 3 → L++
L=3 (0), R=5 (2): 0+2=2 < 3 → L++
L=4 (1), R=5 (2): 1+2=3 == 3 ✓
Found: [-2, -1, 1, 2]
L++, R-- → L=5, R=4, done
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=0 (-2), j=2 (0), pairTarget=2
[-2, _, 0, | 0, 1, 2]
i j L R
L=3 (0), R=5 (2): 0+2=2 == 2 ✓
Found: [-2, 0, 0, 2]
Skip duplicates, L=4, R=4, done
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=0 (-2), j=3 (0): nums[3]==nums[2], SKIP
i=0 (-2), j=4 (1), pairTarget=1
Only one element [2] remains, can't form pair
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=1 (-1), j=2 (0), pairTarget=1
[_, -1, 0, | 0, 1, 2]
i j L R
L=3 (0), R=5 (2): 0+2=2 > 1 → R--
L=3 (0), R=4 (1): 0+1=1 == 1 ✓
Found: [-1, 0, 0, 1]
L=4, R=3, done
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=1, j=3: nums[3]==nums[2], SKIP
i=1, j=4: Only [2] remains
i=2, j=3: nums[2]+nums[3]+min+min = 0+0+1+2 = 3 > 0? Continue.
Actually: 0+0+1+2=3 > 0, and we need sum=0, so skip.
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
✅ Result: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]Deep Insight
**Why O(n³) and not O(n²)?**
We fix TWO elements (i and j), each requiring O(n) iterations. The two-pointer search is O(n). Total: O(n) × O(n) × O(n) = O(n³).
**Generalization to k-Sum:** - 2Sum: Two pointers, O(n) - 3Sum: Fix 1, two pointers, O(n²) - 4Sum: Fix 2, two pointers, O(n³) - kSum: Fix (k-2), two pointers, O(n^(k-1))
**Early termination optimizations:** 1. If `nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target`, break (smallest 4 from i onward exceed target) 2. If `nums[i] + nums[n-3] + nums[n-2] + nums[n-1] < target`, continue (largest 4 with nums[i] still less than target)
Similar optimizations apply to the j loop.
**Integer overflow:** When summing four integers, the result can overflow int. Use `long` for intermediate sums.
**Duplicate handling:** Triple-nested skip logic: - Skip duplicate i values - Skip duplicate j values - Skip duplicate left/right values after finding a match
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n⁴) | O(k) for result set | Four nested loops, set for deduplication |
| Optimal | O(n³) | O(1) excluding output | Two fixed elements O(n²) × two-pointer O(n) |
Pattern Recognition
✅ Find quadruplets with specific sum ✅ Need all unique combinations ✅ Array can be sorted ✅ Extension of 3Sum pattern **LeetCode Trigger Phrases:** → "four numbers... sum equals target" → "all unique quadruplets" → "4Sum" or "four integers in the array"
Bhagavad Gita 4.13
चातुर्वर्ण्यं मया सृष्टं गुणकर्मविभागशः। तस्य कर्तारमपि मां विद्ध्यकर्तारमव्ययम्॥
The four varnas were created by Me according to the differentiation of guna and karma. Though I am the creator of this system, know Me to be the non-doer and immutable.
Connection: The algorithm creates a four-part structure from undifferentiated elements—sorting and separating values just as the four varnas organize society. Each element finds its place through the systematic process: the first fixed, the second fixed, then two more found through the dance of pointers. Yet the algorithm itself, like Krishna, is the 'non-doer'—it merely reveals the quadruplets that were always mathematically inherent in the array.