Given an array, find any three numbers which sum to zero

Given an array, find any three numbers which sum to zero.

This problem is a continuation of a code kata in Python . I'm learning Scala and would like feedback on more efficient, cleaner, and functional ways of solving (and unit testing) this problem.

SumToZero.scala

class SumToZeroNotFound(msg:String=null, cause:Throwable=null)
  extends java.lang.Exception (msg, cause) {}

class SumToZero{
  def process(arr: Array[Int], size: Int = 3): Array[Int] = {
    for(combination <- arr.combinations(size))
      if(combination.sum == 0)  //note: can yield combinations here if we want to find all combinations that sum to zero
        return combination
    throw new SumToZeroNotFound()
  }
}

TestSumToZero.scala

import org.junit.runner.RunWith
import org.scalatest.junit._
import org.scalatest._
import scala.runtime.ScalaRunTime.stringOf

@RunWith(classOf[JUnitRunner])
class TestSumToZero extends FunSuite {

  test("should return entire array that sums to zero") {
    val stz = new SumToZero
      val res = stz.process(Array(1,2,-3))
      val str_res = stringOf(res)
        assert( str_res == "Array(1, 2, -3)",
            "res: " + str_res)
  }

  test("should raise NotFound exception if no combination sums to zero"){
    val stz = new SumToZero
    intercept[SumToZeroNotFound]{
      stz.process(Array(1,2,3,4))
    }
  }

  test("should return first set of nums that sum to zero"){
    val stz = new SumToZero
    val res = stz.process(Array(125, 124, -100, -25, 1, 2, -3, 10, 100))
    val str_res = stringOf(res)
    assert( str_res == "Array(125, -100, -25)",
      "res: " + str_res)
  }
}

Updated SumToZero.scala

```
class SumToZeroNotFound(msg:String=null, cause:Throwable=null)
extends java.lang.Exception (msg, cause) {}

trait SumToZero{

@throws(classOf[SumToZeroNotFound])
def process(arr: Array[Int], size: Int = 3): Array[Int]
}

object SumToZeroBruteForce extends SumToZero{
//brute force process any size combination
override def proces

Since this is tagged 'algorithm' I am going to review your algorithm....

Your algorithm here is wrong. Looking for all combinations (O(n!)) is a very expensive way of doing it. I know very little about Scala, but, can assure you that a much better (the best?) algorithm would be something like:

• sort the data (O(n log(n)))

• 'first' loop through all the values

• 'nested' loop through all values after the value in the 'first' loop

• binary search for the value - (first + nested) in all the values after the nested value

In Java it would be something like:

Arrays.sort(data);
for (int i = 0; i = 0) {
            System.out.printf("Zero-sum values are [%d,%d,%d]\n", data[i], data[j], data[pos]);
        }
    }
}

This has a much better performance characteristic than checking every combination.

You can also add some tricks / optimizations to the loops to quit when impossible combinations present themselves, like:

if (data[i] > 0) {
    // if the smallest value is positive then no possible combination exists....
    break;
}

additionally, you can short-circuit the 'j' loop....

for (int i = 0; i  0) {
        break;
    }
    int maxj = data[data.length - 1] - data[i]; 
    for (int j = i + 1; j < data.length && data[j] <= maxj; j++) {
        .......
    }
}

how you do this in Scala is your problem .... ;-)

StackExchange Code Review Q#37922, answer score: 4