Calculation of Minimum sum using recursion.

Minsum.scala

object Minsum extends App{
   def sum(ls: List[Int]) = ls.foldLeft(0)(_ + _)

  def getMin (numbers: List[Int]): (Boolean,  Int, List[Int]) = {
    val total = sum(numbers)
    def partition(ls: List[Int], nls: List[Int], sum: Int): (Boolean, Int, List[Int]) = {
      ls match {
        case Nil => if (sum >= 0) (true, sum, nls) else (false, sum, nls)  // End of the List => if sum >= 0, return true
        case x :: xs if x > sum => partition(xs, nls, sum) // not ìncluding x in the partitioning set nls
        case x :: xs => {
          val (b1, min1, nls1) = partition(xs, x :: nls, sum - x)
          val (b2, min2, nls2) = partition(xs, nls, sum)
          (b1, b2) match {
            case (true, true) => if (min1 <= min2) (b1, min1, nls1) else (b2, min2, nls2)
            case (true, false) => (b1, min1, nls1) // including current element at partition => gets to minimum
            case (false, true) => (b2, min2, nls2) // excluding current element =?  gets to minimum
            case (_, _) => (false, sum, nls) // nothing changed.
          }
        }
      }
    }
    val (res, _, opt)  = partition(numbers, List(), total/2)
    (res, total-2*opt.sum, opt)
  }

  def printMinimum(ls:List[Int]) = {
    val (res, sum, partition)  = getMin(ls)
    if (res == true)
      println(s"$ls-$partition === $sum")
    else
      println(s"No minimum found. ")
  }
  printMinimum(List(1,5,10))
  printMinimum(List(2,3,4,7,13))
  printMinimum(List(1, 2, 2, 3, 4))
  printMinimum(List(1, 2, 2, 3, 4,4,5,6,6,7,9))

}

Problem Definition:

Given an array of n positive numbers (n ~ 100000), what is the algorithmic approach to find the minimum possible sum (>=0) by using all the numbers in an array?

Example 1:1 2 2 3 4
Answer : 0 (-1+2-2-3+4)

Example 2:2 3 4 7 13
Answer: 1 (+2-3-4-7+13)

Output:

List(1, 5, 10)-List(5, 1) === 4
List(2, 3, 4, 7, 13)-List(7, 4, 3) === 1
List(1, 2, 2, 3, 4)-List(3, 2, 1) === 0
List(1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 9)-List(7, 5, 4, 3, 2, 2, 1) === 1