# 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 (compatible versions 2.13 & 3.0), showing how concise Scala can be!

## 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.

# Scala Algorithms: The most comprehensive library of algorithms in standard pure-functional Scala

### Study our 89 Scala Algorithms: 6 fully free, 89 published & 0 upcoming

Fully unit-tested, with explanations and relevant concepts; new algorithms published about once a week.

### Explore the 21 most useful Scala concepts

To save you going through various tutorials, we cherry-picked the most useful Scala concepts in a consistent form.

## Register now (free)

Register with GitHub

This gives you access to free test cases & hints for all our 89 published algorithms as well as our installation-free Scala IDE.

You can then choose to subscribe to "Scala Algorithms Unlimited", which gets you access to every current and upcoming algorithm solution. We use Stripe so your data is safe.

We will e-mail you at most once per week with new algorithms and relevant content.
Your data is protected and unsubscribing is straightforward. 