subssum.rb

def subssum(nums, sum)
    dp = Array.new(nums.size+1){Array.new(sum+1)}
    dp[0][0] = []
    nums.size.times do|i|
        dp[i].each_index do|j|
            if dp[i][j]
                dp[i+1][j] = dp[i][j]
                if j+nums[i] <= sum
                    dp[i+1][j+nums[i]] = dp[i][j]+[nums[i]]
                end
            end
        end
    end
    return dp.last.last
end
def subssums(nums, sum)
    dp = Array.new(nums.size+1){Array.new(sum+1){[]}}
    dp[0][0] << []
    nums.size.times do|i|
        dp[i].each_index do|j|
            dp[i][j].each do|k|
                dp[i+1][j] << k
                if j+nums[i] <= sum
                    dp[i+1][j+nums[i]] << k+[nums[i]]
                end
            end
        end
    end
    return dp.last.last
end
p subssum([1,3,7,10,13], 21)
p subssums([1,3,7,10,13], 21)