How to solve UVa 1099:Square problem?

Here the link of the problem.I think we need to use dp+bitmask in some way.Please give me some hints/sols if you can solve it?Shortened problem description:

A bar of chocolate consist of many small 'unit' pieces.Give a bar of chocolate size x*y pieces. There are n friends,each of your friends insists on a getting a single rectangular portion of the chocolate that has a specified number of pieces that have exactly ai 'unit' pieces. Is there a way to split the original bar of chocolate into n pieces,each have exactly ai 'unit' pieces? (Constraints: 1≤n≤15 && 1≤x,y≤100).
1 Like