動的計画法を使った部分和（解説を見て）

partsum.rb

#!/usr/bin/env ruby

n = gets.chomp.to_i
a = gets.chomp.split(/ /).map(&:to_i)
ans = gets.chomp.to_i
dp = []
(0..n).each do |i|
  dp << []
  (0..ans).each do |a|
    dp[i][a] = false
  end
end
dp[0][0] = true

#dp[i番目までのいくつか][j]になるか
(0..(n - 1)).each do |i|
  (0..ans).each do |aa|
    dp[i + 1][aa] = dp[i][aa]
    if(aa >= a[i])
      dp[i + 1][aa] ||= dp[i][aa - a[i]]
    end
  end
end
puts dp[n][ans]