Recursive "Carnac" solution in Ruby

output.txt

1 + 2 + 3 - 4 + 5 + 6 + 78 + 9
1 + 2 + 34 - 5 + 67 - 8 + 9
1 + 23 - 4 + 5 + 6 + 78 - 9
1 + 23 - 4 + 56 + 7 + 8 + 9
12 + 3 + 4 + 5 - 6 - 7 + 89
12 + 3 - 4 + 5 + 67 + 8 + 9
12 - 3 - 4 + 5 - 6 + 7 + 89
123 + 4 - 5 + 67 - 89
123 - 4 - 5 - 6 - 7 + 8 - 9
123 + 45 - 67 + 8 - 9
123 - 45 - 67 + 89

solutions.rb

def solutions(acc, rem)
  if rem.size == 0
    if sum_array_with_operators(acc.reverse) == 100
      puts acc.join(" ")
    end
  else
    head, *tail = *rem

    if acc.size == 0
      # get things going
      solutions([head], tail)
    else
      # +
      solutions(acc + [:+, head], tail)
      # -
      solutions(acc + [:-, head], tail)
    end

    # concatenate
    if tail.size > 0
      tail[0] = (head * 10) + tail[0]
      solutions(acc, tail)
    end
  end
end

# Arrives like this: [1, :+, 2, :-, 3, :+, 5]
def sum_array_with_operators(arr)
  if arr.size == 1
    arr[0]
  else
    num, operator, *tail = *arr
    sum_array_with_operators(tail).send(operator, num)
  end
end

solutions([], (1..9).to_a)