Skip to content

Instantly share code, notes, and snippets.

@nicmart
Created March 20, 2017 16:45
Show Gist options
  • Save nicmart/8d57a24952cae0bbb2ebbdaf860b377c to your computer and use it in GitHub Desktop.
Save nicmart/8d57a24952cae0bbb2ebbdaf860b377c to your computer and use it in GitHub Desktop.
Partitions
def partitions(n: Int): List[List[Int]] = partitionsGreaterThan(n, 1)
def partitionsGreaterThan(n: Int, m: Int): List[List[Int]] = n match {
case _ if m > n => List()
case _ if m == n => List(List(n))
case _ if m < n =>
val ns1 = partitionsGreaterThan(n - m, m).map { m :: _ }
val ns2 = partitionsGreaterThan(n, m + 1)
ns1 ::: ns2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment