Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def subsetSum(numbers: List[Int], target: Int, partial: List[Int] = List.empty, partialSum: Int = 0): List[Int] = {
- if (partialSum == target) {
- partial
- } else if (partialSum >= target) {
- List.empty
- } else {
- val possibleSums = (for {
- n <- numbers
- remaining = exceptFirst(numbers, n)
- } yield subsetSum(remaining, target, partial :+ n, partialSum + n)).filter(_.nonEmpty)
- if (possibleSums.isEmpty) {
- List.empty
- } else {
- possibleSums.sortBy(_.size).head
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement