Hey,

recently I came across a problem which is described below. I've been struggling with it for a while. Could You please help me by giving some hints?

You are given n squares of certain sizes and have to create a larger square using all of those smaller squares. By that I mean that you can connect these squares however you want, so that it results in one large square. Input looks in the following way: first line contains n (it was not explicitly stated what is the max value of n, but it is something in range <30, 90>) and second line contains n integers (each of value from 1 to 50) each describes size of i-th square. As output you have to write either "YES" if it is possible to create a square from all the smaller squares or "NO" if it is impossible.

At first I thought that it's some kind of dynamic programming, but I believe that it'd be hard to keep track of squares which where used to create some state in DP. I'm also not convinced about some greedy approach, like take largest square which haven't been used and place it in first empty position, because that would be to easy and I know that these kind of tasks require more thinking. So I'm thinking that maybe some backtracking approach would be the right choice, though I'm not sure about that. Could You please help me with this task?

Example tests:

INPUT

6
1 1 1 2 1 1

OUTPUT

YES

INPUT

3
5 5 5

OUTPUT

NO