In this blog post, we will attempt to address the 4-Sum problem from Leet code using the generic approach of K-Sum. Let us state the official definition of the problem.
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2:
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]
Two-Sum Problem
The core to address the problem is to reduce the problem to a 2-sum problem. As per the Two-Sum problem definition, we need to find all the pairs of numbers from the list, which adds up to the given target. There are few approaches to the same, which includes
- Binary Search
- Using two pointers
- Using Mapping
In this example, we will use the third approach. Let us go ahead and define our solution for the Two-Sum Problem.
public IEnumerable<int[]> TwoSum(int[] items, int target)
{
Dictionary<int,int> mapping = new ();
for(int i=0;i<items.Length;i++)
{
var expected = target- items[i];;
if(mapping.TryGetValue(expected, out var val))
{
yield return new int[]{items[i], expected};
}
mapping[items[i]] = expected;
}
}
For any given array of numbers items, this method would return the pair of numbers (if any) that adds to the given target.
3-Sum, 4-Sum…..K-Sum
Now that we have tacked the 2-Sum problem, we will look into higher ranges starting with 3-Sum, 4-Sum and so on. Let us consider the 3-Sum problem first. Given an array of numbers, We would need find the triplets which adds to the given target.
The problem can also be stated as, for any given array of sorted numbers items and num where is a number within items (with index i), we need to find a pair of numbers which adds to target – num where the source array is a sub-array of items starting from index i. In other words, we reduced our 3-Sum problem to a 2-Sum problem.
Similiarly, a 4-Sum can be reduced to a 3-Sum problem, which can be further reduced to a 2-sum problem. In other words, we can reduce any K-Sum problem to 2-Sum problem by recurisively reducing it to a K-1 problem until it is a 2-Sum problem.
Following code provides a solution to our K-Sum Problem, by reducing it to a 2-Sum problem.
public class Solution
{
// Solution to 4-Sum using K-Sum
public IList<IList<int>> FourSum(int[] nums,int target)
{
Array.Sort(nums);
var result = new Dictionary<string,IList<int>>();
foreach(var item in KSum(nums,4,target))
{
var key = string.Join(",",item);
if(!result.ContainsKey(key))
{
result.Add(key,item);
}
}
return result.Values.ToList();
}
// Generic K-Sum solution
public IEnumerable<IList<int>> KSum(int[] nums,int k,int target)
{
if(k<2 || nums.Length < 2) yield break;
if(k==2)
{
// we have reduced the problem to a 2-Sum Problem. Find pairs now.
foreach(var subResult in TwoSum(nums.ToArray(),target))
{
yield return subResult;
}
}
else
{
for(int i=0;i<nums.Length;i++)
{
// This is to check overflow arithmetic exceptions
if(!IsValidRange(target, nums[i])) yield break;
// Reduce to a K-1 Problem
foreach(var subResult in KSum(nums.Skip(i+1).ToArray(),k-1,target-nums[i]))
{
if(subResult.Any())
{
var result = new List<int>();
result.Add(nums[i]);
result.AddRange(subResult);
yield return result;
}
}
}
}
}
public IEnumerable<int[]> TwoSum(int[] items, int target)
{
Dictionary<int,int> mapping = new ();
for(int i=0;i<items.Length;i++)
{
var expected = target- items[i];;
if(mapping.TryGetValue(expected, out var val))
{
yield return new int[]{items[i], expected};
}
mapping[items[i]] = expected;
}
}
private bool IsValidRange(int first,int second)
{
var temp = (long)first - (long)second;
return (temp < Int32.MaxValue && temp > Int32.MinValue);
}
}
So we you can see from the code, we have created a K-Sum solution for our 4-Sum problem.
ByteLanguage.Net 