部分和

dp.rb

#!/usr/bin/env ruby

n = gets.chomp.to_i
a = gets.chomp.split(/ /).map(&:to_i)
ans = gets.chomp.to_i

dp= []
sums = []
(0..(n - 1)).each do |i|
  if(dp[ans - a[i]] && (ans - a[i]) > 0)
    puts 'YES'
    exit
  else
    dp[a[i]] = 1
    newsums = sums.dup
    sums.each do |j|
      dp[a[i] + j] = 1
      newsums << a[i] + j
    end
    sums = newsums
  end
end
puts "NO"