Question

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

Answer 1

# Print a partition stored in 'arr' in the form "a + b + c"
def print_array(arr, size)
  line = ""

  (0...size).each do |i|
    line += " + " if i > 0   # add plus signs between numbers
    line += arr[i].to_s
  end

  puts line
end

=begin
    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.
=end
def partitions(arr, size, start, remaining)

  # Base case: exact sum reached
  if remaining == 0
    if size >= 2      # enforce "two or more integers"
      print_array(arr, size)
    end
    return
  end

  # Try all next values from 'start' up to 'remaining'
  (start..remaining).each do |j|
    arr[size] = j                          # choose j
    partitions(arr, size + 1, j, remaining - j)  # recurse with reduced remainder
    # no need to "pop" in Ruby; we just overwrite next time
  end
end

def main
  n = 5                 # number to partition
  arr = Array.new(128, 0)  # holds current partition (large enough buffer)

  partitions(arr, 0, 1, n)  # start with smallest allowed value = 1
end

main


=begin
run:

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

=end

 

70+ SQL courses for beginners and professionals

Answer 2

# Generate all ways to write n as a sum of positive integers.
# Each partition is non‑decreasing (e.g., [1,2,2] instead of [2,1,2]).
def partitions(n)
  result = []   # stores all completed partitions
  current = []  # current partial partition being built

  # Recursive helper:
  # remaining — how much is left to reach n
  # start — the minimum next value allowed (enforces non‑decreasing order)
  backtrack = lambda do |remaining, start|
    # If nothing is left, we found a valid partition
    if remaining == 0
      result << current.dup   # store a copy because current will change
      return
    end

    # Try all possible next values from `start` up to `remaining`
    (start..remaining).each do |i|
      current << i                 # choose i
      backtrack.call(remaining - i, i)  # recurse with reduced remainder
      current.pop                  # undo the choice (backtrack)
    end
  end

  # Start building partitions with minimum allowed value = 1
  backtrack.call(n, 1)
  result
end


n = 5
partitions(n).each { |p| p p }



=begin
run:

[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 3]
[1, 2, 2]
[1, 4]
[2, 3]
[5]

=end

 

70+ SQL courses for beginners and professionals