部分和問題

subset_sum_problem1.rb

## 部分和問題
## http://rubyfiddle.com/riddles/2083e

# 配列の大きさ。rubyだと簡単に求められるので使う機会がない。
n = 4
# カンマ区切りで[ ]の中の値を変えてみてね！
# ex. [1, 2, 3, 4, 8, 10, 12]
a = [ 1, 2 , 4, 7]
# 求める和。好きな数字に変えてみよう！半角数字でお願いします。
k = 13

# 解答はあらかじめ No にしておく
ans = "No"

# 1から整数の個数のあいだ繰り返す。i には繰り返しの回数が入る。
1.upto(a.size){|i|
  
  # すでに答えが求められていたら繰り返しを抜ける。
  if ans == "Yes"
    break
  end
  
  # 整数の組み合わせを i の回数個求める。
  a.combination(i){|j|
    
    v = 0
    
    #　[1, 2, 4]などの組み合わせで求めた数を合計する。
    j.each{|m|
      v += m
      }
    
    # 合計と求める和が等しければ解答に Yes を代入する
    if v == k
      ans = "Yes"
      break
    end
    }
  }
# 解答を出力する。
# 解答に"Yes"が代入されていなければ10行目の”No"が出力される。
puts ans