2
\$\begingroup\$

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;
}
\$\endgroup\$
2
\$\begingroup\$

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...

\$\endgroup\$
  • \$\begingroup\$ 3 * maxInput could be bigger than int \$\endgroup\$ – paparazzo Mar 26 '18 at 8:00
  • \$\begingroup\$ @paparazzo: OK, I see, it's easier your way - changed my answer. \$\endgroup\$ – Henrik Hansen Mar 26 '18 at 8:16
  • \$\begingroup\$ If I don't get any more answers by tomorrow I will accept. \$\endgroup\$ – paparazzo Mar 26 '18 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.