4Sum passing with N^3 * LogN

Revisited an old problem: https://leetcode.com/problems/4sum/description/

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

It failed for me 2 years back when I tried a simple N^4 solution (four nested for loops). An optimization for the last loop - using Binary Search instead of a loop - made the trick, bringing the complexity down to N^3 * LogN, good enough to pass. Cheers, ACC.

public class Solution
{
public IList<IList<int>> FourSum(int[] nums, int target)
{
if (nums == null || nums.Length == 0) return new List<IList<int>>();

Hashtable htSolutions = new Hashtable();
List<IList<int>> solutions = new List<IList<int>>();

Array.Sort(nums);
long t = (long)target;

long partialSum = 0;

if (target >= 0)
{
for (int a = 0; a < nums.Length; a++)
{
partialSum += nums[a];
if (partialSum > t)
{
partialSum -= nums[a];
break;
}

for (int b = a + 1; b < nums.Length; b++)
{
partialSum += nums[b];
if (partialSum > t)
{
partialSum -= nums[b];
break;
}

for (int c = b + 1; c < nums.Length; c++)
{
partialSum += nums[c];
if (partialSum > t)
{
partialSum -= nums[c];
break;
}

if (BinarySearch(nums, c + 1, nums.Length - 1, target - partialSum))
{
string key = nums[a].ToString() + "@" + nums[b].ToString() + "@" + nums[c].ToString() + "@" + (target - partialSum).ToString();
if (!htSolutions.ContainsKey(key))
{
List<int> list = new List<int>();
list.Add(nums[a]);
list.Add(nums[b]);
list.Add(nums[c]);
list.Add((int)(target - partialSum));
solutions.Add(list);
htSolutions.Add(key, true);
}
}

partialSum -= nums[c];
}

partialSum -= nums[b];
}

partialSum -= nums[a];
}
}
else
{
for (int a = nums.Length - 1; a >= 0; a--)
{
partialSum += nums[a];
if (partialSum < t)
{
partialSum -= nums[a];
break;
}

for (int b = a - 1; b >= 0; b--)
{
partialSum += nums[b];
if (partialSum < t)
{
partialSum -= nums[b];
break;
}

for (int c = b - 1; c >= 0; c--)
{
partialSum += nums[c];
if (partialSum < t)
{
partialSum -= nums[c];
break;
}

if (BinarySearch(nums, 0, c - 1, target - partialSum))
{
string key = nums[a].ToString() + "@" + nums[b].ToString() + "@" + nums[c].ToString() + "@" + (target - partialSum).ToString();
if (!htSolutions.ContainsKey(key))
{
List<int> list = new List<int>();
list.Add(nums[a]);
list.Add(nums[b]);
list.Add(nums[c]);
list.Add((int)(target - partialSum));
solutions.Add(list);
htSolutions.Add(key, true);
}
}

partialSum -= nums[c];
}

partialSum -= nums[b];
}

partialSum -= nums[a];
}
}
return solutions;
}

private bool BinarySearch(int[] nums,
int left,
int right,
long target)
{
while (left >= 0 &&
left < nums.Length &&
right >= 0 &&
right < nums.Length &&
left <= right)
{
int mid = (left + right) / 2;
if (nums[mid] == target) return true;
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}

return false;
}
}