problem5.rb

# http://www.softantenna.com/wp/software/5-programming-problems/
# https://blog.svpino.com/2015/05/07/five-programming-problems-every-software-engineer-should-be-able-to-solve-in-less-than-1-hour
#
# 問題4
# 1,2,…,9の数をこの順序で、”+”、”-“、またはななにもせず結果が100となるあらゆる組合せを出力するプログラムを記述せよ。
# 例えば、1 + 2 + 34 – 5 + 67 – 8 + 9 = 100となる(解答例)

@list = (1..9).to_a
@result_all = []

# @param [Array] list
def func1(list)
  create_all_combinations(list, [])
  @result_all.each do |candidate|
    compute(candidate, '', 0)
  end
end

# @param [Array] candidate
# @param [String] exp
# @param [Fixnum] result
def compute(candidate, exp, result)
   # p "candidate = #{candidate}"
   # p "exp = #{exp}"
   # p "result = #{result}"

  if candidate.empty?
    # p "*** #{exp}=#{result} ***"
    if result == 100
      p "#{exp}=#{result}"
    end
    return
  end

  val = candidate.first.to_i
  remains = candidate.last(candidate.length - 1)
  if exp.empty?
    compute(remains, "#{val}", val)

  else
    compute(remains, "#{exp}+#{val}", result + val)
    compute(remains, "#{exp}-#{val}", result - val)
  end
end

# @param [Array] list
# @param [Array] result
def create_all_combinations(list, result)
  # p "list = #{list}"
  # p "result = #{result}"
  if list.empty?
    # p "result = #{result}"
    @result_all.push(result)
    return
  end
  list.each_with_index do |val, idx|
    val_string = list.first(idx + 1).reduce('') {|total, num|
      total + "#{num}"
    }
    create_all_combinations(list.last(list.length - idx - 1), [result, val_string].flatten)
  end
end


func1(@list.dup)