# Determine if a partition of integer using given parts exists

Is there a way to determine if a partition of integer $n$ into a given set of integers (represented by a vector $\mathbf{x}$) exists, other than enumerating all partitions of $n$ and checking if one matches $\mathbf{x}$?

For instance, I have $\mathbf{x} = (3, 7)$ and I want to know if $1000$ can be written as a sum $\sum_{i=1} \mathbf{x}_i \cdot \mathbf{k}_i$, where $\mathbf{k}_i$ are the multiplicities of the parts.

I'm not really interested in finding the number of those partitions or enumerating them all. I'm only interested to find if one exists. I was unable to find any literature on this at all.

So far, I only came up with $0 \ge \mathbf{k}_i \ge \lfloor \frac{n}{\mathbf{x}_i} \rfloor$ and I'm just enumerating all possible combinations of $\mathbf{k}_i$ for $i \ge 2$ until I find / do not find one that sums up to $n - m \cdot \mathbf{x}_1$ with $m$ being a positive integer (can test for that quickly by dividing $n - \sum_{i=2} \mathbf{x}_i \cdot \mathbf{k}_i$ by $\mathbf{x}_1$ and checking if there is a remainder ... that saves me some combinations). It works for reasonably small numbers but it is not horribly elegant.

This is the coin problem. If your vector is of length $2$, there is a good solution. If the values are coprime, the largest number that cannot be represented is $x_1x_2-x_1-x_2$. If they are not coprime, your target must be divisible by the $\gcd$, then divide the target and the values by that $\gcd$. For longer vectors it is not easy.