require 'pp' $ws = [] $n = 0 $dp = {} def main $n = gets.to_i $ws = gets.strip.split(' ').map{|e| e.to_i} $n.times{|i| $dp[i] = {}} sum = $ws.reduce(:+) result = solve(0, 0, sum) puts result ? "possible" : "impossible" end def solve(i, acc, sum) if (i === $n) return false end if $dp[i].key?(acc) return $dp[i][acc] end if (sum % 2 === 1) return false end if (acc * 2 === sum) return true end nex = $ws[i] result = solve(i + 1, acc + nex, sum) || solve(i + 1, acc, sum) $dp[i][acc] = result end main()