Уплатить единственным способом

[Ktina]

В 80-е годы в СССР имелись в обращении монеты в 1, 2, 3, 5, 10, 15, 20, 50 копеек, а также монета в 1 рубль.
Следовательно, существовали денежные суммы, которые можно было лишь единственным способом уплатить монетами, среди которых нет двух одинаковых.
Скучным и нудным перебором мне удалось найти несколько таких сумм. Это 1, 2, 4, 7, 9, 12, 14, 42, 44, 47, 49, 57, 59, 62, 64, 92, 94, 97 и 99 копеек.

Можно ли обойтись без перебора? И как найти все требуемые суммы?
Пожалуйста, помогите решить!
Заранее спасибо!

[DeBill]

А это не есть, случайно, ужасная Задача про укладку рюкзака (которая тем и ужасна, что нет для нее хороших алгоритмов)?

[mihaild]

Это чуть сложнее, чем рюкзак - за счет требования уникальности: сведение $3SAT$ к $SUBSETSUM$ сохраняет число решений (и его можно сделать таким, чтобы все веса были различны), так что эта задача эквивалентна $UNIQUE-SAT$, которая $NP$ и $coNP$ трудна.

Решается той же стандартной динамикой, что и рюкзак: считаем функцию $f(n, m)$ - число способов получить сумму $n$, используя первые $m$ монет; $f(n, -1) = \delta_{0, n}, f(n, m + 1) = f(n, m) + f(n - p_{m + 1}, m)$ (при этом достаточно помнить только три варианта значения: $0, 1, >1$).