Find sum of 3 that total a target from a List

Question

A related Java question got me curios.

All unique combinations (not permutations) of 3 values that sum to a target from a list of integers.

Values can duplicate in the list but are only used once.

By sorting the input the evaluation is able to take shortcuts.

Feedback on both code and speed please.

Assume all input and sum>= 0.

public static List<List<int>> FindThreeSum(List<int> input, int sum = 24)
{
 //cannot have default on a list to my knowledge
 if(input.Count < 3)
 {
 input = new List<int> { 8, 12, 6, 18, 4, 3, 8, 1, 6, 3, 8, 9, 0 };
 //in real life throw an error
 }
 List<int> sortedInput = input.OrderBy(x => x).ToList();
 Debug.WriteLine(string.Join(", ", sortedInput));
 int sortedCount = sortedInput.Count;
 int maxInput = sortedInput[sortedCount - 1];
 List<List<int>> findSum = new List<List<int>>();
 if (3 * (long)maxInput < (long)sum || sortedInput[0] < 0 || sum < 0 || 3 * sortedInput[0] > sum)
 {
 return findSum;
 } 
 int sumSoFar;
 int sumI = int.MaxValue; 
 int sumJ = 0;
 int sumK = 0;
 for (int i = 0; i < sortedCount - 2; i++)
 {
 if(sortedInput[i] == sumI)
 {
 continue; 
 }
 sumI = sortedInput[i];
 if(3 * sumI > sum) 
 { 
 break; //sumSoFar is only going to get bigger
 }
 for (int j = i + 1; j < sortedCount - 1; j++)
 {
 if (sortedInput[j] == sumJ)
 {
 continue;
 }
 sumJ = sortedInput[j];
 sumSoFar = sumI + sumJ;
 if (sumSoFar + sumJ > sum)
 {
 break;
 }
 else if(sumSoFar + maxInput < sum)
 {
 continue;
 }
 for (int k = j + 1; k < sortedCount; k++)
 {
 if (sortedInput[k] == sumK)
 {
 continue;
 }
 sumK = sortedInput[k];
 sumSoFar = sumI + sumJ + sumK;
 if (sumSoFar > sum)
 {
 break;
 }
 else if(sumSoFar == sum)
 {
 findSum.Add(new List<int> { sumI, sumJ, sumK });
 Debug.WriteLine($"{sumI} {sumJ} {sumK}");
 }
 }
 }
 }
 Debug.WriteLine("daDone");
 return findSum;
}

Answer 1

In general it looks OK to me, but you could maybe consider the following:

1) Return a IEnumerable<int[]> instead of List<List<int>> and then yield the positive results when found:

 ...
 else if (sumSoFar == sum)
 {
 yield return new int[] { iValue, jValue, kValue };
 }...

2) The names sumI, sumJ, sumK are somewhat misleading because they aren't sums. Better names would be valueI, -J, -K

 int valueI;
 int valueJ;
 int valueK;

3) For the fun of it, you could consider: Because you basically do the same same loop nested three times, it could be a candidate for a recursive function iterating over each addend and yielding all the positive sums. In that way you could generalize the algorithm to handle any number of addends...

• paparazzo: 3 * maxInput could be bigger than int
• user73941: @paparazzo: OK, I see, it's easier your way - changed my answer.
• paparazzo: If I don't get any more answers by tomorrow I will accept.