$n = gets.to_i $w = gets.split.map(&:to_i) $nerai = $w.inject(:+)/2.0 $dp = Array.new($n){Array.new(100*100, nil)} def dfs(depth, total) if depth >= $n - 1 return total + $w[depth] if total + $w[depth] == $nerai return total if total == $nerai return -1 end a = $dp[depth+1][total+$w[depth]].nil? ? dfs(depth+1, total+$w[depth]) : $dp[depth+1][total+$w[depth]] b = $dp[depth+1][total].nil? ? dfs(depth+1, total) : $dp[depth+1][total] return a if $nerai == a return b if $nerai == b return -1 end puts dfs(-1, 0) > 0 ? "possible" : "impossible"