v2ex-835261-leetcode-416.rb

# @param {Integer[]} nums
# @return {Boolean}
def can_partition(nums)
    sum = nums.sum
    return false if sum.odd?
    nums.sort!
    nums.reverse!
    half_sum = sum / 2
    dp = Set.new
    0.upto(nums.size-1) do |i|
        num = nums[i]
        dp += dp.map { |x| x + num }
        dp << num
        return true if dp.include?(half_sum)
        dp.delete_if { |x| x > half_sum}
    end
    false
end