Maximum Ribbon Cut

Statement

Given a ribbon of length n and a set of possible sizes, cut the ribbon in sizes such that n is achieved with the maximum number of pieces.

You have to return the maximum number of pieces that can make up n by using any combination of the available sizes. If the n can’t be made up, return -1, and if n is 0, return 0.

Let’s say, we have a ribbon of length $13$ and possible sizes as $[5, 3, 8]$. The ribbon length can be obtained by cutting it into one piece of length $5$ and another of length $8$ (as $5 + 8 = 13$), or, into one piece of length $3$ and two pieces of length $5$ (as $3 + 5 + 5 = 13$). As we wish to maximize the number of pieces, we choose the second option, cutting the ribbon into $3$ pieces.

Constraints:

• $1 \leq$ sizes.length $\leq 12$

• $1 \leq$ sizes[i] $\leq 2^{31} -1$

• $0 \leq$ n $\leq 1500$

Examples