Question

How to find all possible ways to write a positive integer as a sum of positive integers in Scala

Answer 1

// Print a partition stored in 'arr' in the form "a + b + c"
def printArray(arr: Array[Int], size: Int): Unit = {
  val sb = new StringBuilder

  for (i <- 0 until size) {
    if (i > 0) sb.append(" + ")   // add plus signs between numbers
    sb.append(arr(i).toString)
  }

  println(sb.toString)
}

/*
    Generate all partitions of a number using non-decreasing sequences.

    arr       – current partial partition being built
    size      – how many elements are currently in arr
    start     – the smallest number allowed next (prevents duplicates like 2+1 vs 1+2)
    remaining – how much is left to reach the target sum

    When remaining == 0, arr contains a complete valid partition.
*/
def partitions(arr: Array[Int], size: Int, start: Int, remaining: Int): Unit = {

  // Base case: exact sum reached
  if (remaining == 0) {
    if (size >= 2)      // enforce "two or more integers"
      printArray(arr, size)
    return
  }

  // Try all next values from 'start' up to 'remaining'
  for (j <- start to remaining) {
    arr(size) = j                          // choose j
    partitions(arr, size + 1, j, remaining - j)  // recurse with reduced remainder
    // no need to "pop" in Scala; we just overwrite next time
  }
}

@main def main(): Unit = {
  val n: Int = 5                 // number to partition
  val arr: Array[Int] = Array.fill(128)(0)  // holds current partition (large enough buffer)

  partitions(arr, 0, 1, n)       // start with smallest allowed value = 1
}


/*
run:

1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 2
1 + 1 + 3
1 + 2 + 2
1 + 4
2 + 3

*/

 

70+ SQL courses for beginners and professionals

Answer 2

object IntegerPartitions {

  // Generate all partitions of n
  def partitions(n: Int): List[List[Int]] = {

    // Helper function:
    // remaining = number left to partition
    // maxAllowed = largest number we may use next (to keep non-increasing order)
    def loop(remaining: Int, maxAllowed: Int): List[List[Int]] = {
      if (remaining == 0)
        List(Nil) // One valid partition: empty list
      else {
        // Try all next numbers k from min(remaining, maxAllowed) down to 1
        (1 to math.min(remaining, maxAllowed)).reverse.toList.flatMap { k =>
          // For each k, partition the rest (remaining - k)
          loop(remaining - k, k).map(k :: _)
        }
      }
    }

    loop(n, n)
  }

  def main(args: Array[String]): Unit = {
    val n = 5
    println(s"Partitions of $n:")
    
    partitions(n).foreach(p => println(p.mkString(" + ")))
  }
}



/*
run:

Partitions of 5:
5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

*/

 

70+ SQL courses for beginners and professionals