Find combinations of an array that sum up to N, where numbers are unique. Support large inputs. For the non-unique version, see FindCombinationsAddingUpTo.
Test cases in Scala
assert(combosList(Set.empty, target = 0).isEmpty) assert(combosList(Set(1, 2, 3), target = 3).toSet == Set(Set(1, 2), Set(3))) assert(combosList(Set(1, 2, 3), target = 7).isEmpty) assert( combosList(Set(1, 2, 3, 4, 5, 6), target = 5).toSet == Set(Set(1, 4), Set(2, 3), Set(5)) ) assert(combosList(Set(2, 1), target = 3).toSet == Set(Set(2, 1)))
Algorithm in Scala
8 lines of Scala (version 2.13), showing how concise Scala can be!
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. (this is © from www.scala-algorithms.com)
Scala concepts & Hints
The for-comprehension is highly important syntatic enhancement in functional programming languages.
The 'LazyList' type (previously known as 'Stream' in Scala) is used to describe a potentially infinite list that evaluates only when necessary ('lazily').