Scala algorithm: Find combinations adding up to N (non-unique)

Published

Algorithm goal

Find combinations of an array that sum up to N. Numbers are not unique. Support large inputs. Represent the set of non-unique values as a multiset, ie Map[Int, Count], where type Count = Int. For the unique items version, see: FindCombinationsAddingUpToUnique.

Test cases in Scala

assert(combosList(Array.empty, target = 0).isEmpty)
assert(
  combosList(Array(1, 2, 3), target = 3).toSet ==
    Set(Map(1 -> 1, 2 -> 1), Map(3 -> 1))
)
assert(
  combosList(Array(1, 1, 1, 2), target = 3).toSet ==
    Set(Map(1 -> 3), Map(1 -> 1, 2 -> 1))
)
assert(
  combosList(Array(2, 1, 1, 1, 2), target = 3).toSet ==
    Set(Map(2 -> 1, 1 -> 1), Map(1 -> 3))
)

Algorithm in Scala

9 lines of Scala (version 2.13), showing how concise Scala can be!

Get the full algorithm Scala algorithms logo, maze part, which looks quirky!

or

'Unlimited Scala Algorithms' gives you access to all the Scala Algorithms!

Upon purchase, you will be able to Register an account to access all the algorithms on multiple devices.

Stripe logo

Explanation

The Scala solution is quite elegant and expressive as well as stack-safe due to the fact that there is no recursion (many languages have a solution but the solution is often using recursion).

Scala provides a 'combinations' method on Array, given a selection length; then the only thing we need to vary is the selection length, which we can produce using a Lazy List. Then, using a for-comprehension and a guard we check if the target of what we are looking for is met, and return that combination if it is.In generating the combination, we use a way to group items, and the extract the count of members in each group. (this is © from www.scala-algorithms.com)

Scala concepts & Hints

  1. For-comprehension

    The for-comprehension is highly important syntatic enhancement in functional programming languages.

    val Multiplier = 10
    
    val result: List[Int] = for {
      num <- List(1, 2, 3)
      anotherNum <-
        List(num * Multiplier - 1, num * Multiplier, num * Multiplier + 1)
    } yield anotherNum + 1
    
    assert(result == List(10, 11, 12, 20, 21, 22, 30, 31, 32))
    
  2. Lazy List

    The 'LazyList' type (previously known as 'Stream' in Scala) is used to describe a potentially infinite list that evaluates only when necessary ('lazily').

  3. View

    The .view syntax creates a structure that mirrors another structure, until "forced" by an eager operation like .toList, .foreach, .forall, .count.

View the rest of Scala algorithms