Advertisement
Guest User

Untitled

a guest
Mar 20th, 2017
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Scala 0.55 KB | None | 0 0
  1.   def subsetSum(numbers: List[Int], target: Int, partial: List[Int] = List.empty, partialSum: Int = 0): List[Int] = {
  2.     if (partialSum == target) {
  3.       partial
  4.     } else if (partialSum >= target) {
  5.       List.empty
  6.     } else {
  7.       val possibleSums = (for {
  8.         n <- numbers
  9.         remaining = exceptFirst(numbers, n)
  10.       } yield subsetSum(remaining, target, partial :+ n, partialSum + n)).filter(_.nonEmpty)
  11.       if (possibleSums.isEmpty) {
  12.         List.empty
  13.       } else {
  14.         possibleSums.sortBy(_.size).head
  15.       }
  16.     }
  17.   }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement