Problem 5 recursive solution

problem5.rb

# Write a program that outputs all possibilities to put + or - or nothing
# between the numbers 1, 2, ..., 9 (in this order) such that the result is
# always 100. For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.

# 1 + [2..9]
# 1 - [2..9]
# 12 + [3..9]
# 12 - [3..9]
# 123 + [4..9]
# 123 - [4..9]
# ...
# 1 + (2 + [3..9])
# 1 + (2 - [3..9])
# 1 + (23 + [4..9])
# 1 + (23 - [4..9])
# 1 + (234 + [5..9])
# 1 + (234 - [5..9])
# 1 - (2 + [3..9])
# 1 - (2 - [3..9])
# 1 - (23 + [4..9])
# 1 - (23 - [4..9])
# 1 - (234 + [5..9])
# 1 - (234 - [5..9])
# ...
# 12 + 3 + [4..9]
# 12 + 3 - [4..9]
# 12 - 3 + [4..9]
# 12 - 3 + [4..9]
# 12 + 34 + [5..9
# 12 + 34 - [5..9]
# 12 - 34 + [5..9]
# 12 - 34 - [5..9]
# ...
# 123 + 4 + [5..9]
# 123 + 4 - [5..9]
# 123 - 4 + [5..9]
# 123 - 4 - [5..9]
# 123 + 45 + [6..9]
# 123 + 45 - [6..9]
# 123 - 45 + [6..9]
# 123 - 45 - [6..9]

$solutions = []
def f(nums, string)
  str = string[3..(string.length)]
  $solutions.push(str) if nums.length == 0 && eval(str.strip) == 100
  nums.length.times do |x|
    lv = nums[0..x].join
    f(nums[(x+1)..(nums.length-1)], "#{string} + #{lv}")
    f(nums[(x+1)..(nums.length-1)], "#{string} - #{lv}")
  end
end
f((1..9).to_a, "")
$solutions.uniq.each do |solution|
  puts solution
end