Show problems as
Classic problem #3592MediumArrayDynamic Programming

Inverse Coin Change

Real-world version: Recover the Coin Denominations
Tracked in this browser only
Read Inverse Coin Change on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A mint used a set of coin face values, all distinct positive whole numbers. For an amount a, the number of ways to make a is the number of different multisets of those coins that total exactly a, so order never matters and a face value may be reused freely.

You are given numWays, where numWays[i] is the number of ways to make the amount i + 1. Every face value the mint used is at most numWays.length.

Return the face values the mint used, in increasing order. If no set of face values produces exactly these counts, return an empty list.

Examples

Example 1

Input
numWays = [0, 1, 0, 1, 0]
Output
[2]

With a single face value of 2 the amounts 2 and 4 can each be made one way, using one coin and two coins, while the amounts 1, 3 and 5 cannot be made at all.

Example 2

Input
numWays = [1, 1, 1, 1]
Output
[1]

With a single face value of 1 each of the amounts 1 through 4 can be made exactly one way, by repeating that coin.

Example 3

Input
numWays = [2]
Output
[]

The amount 1 can only ever be made by a single coin of face value 1, so it can never be made two ways and no set of face values fits.

Constraints

  • 1 <= numWays.length <= 100
  • 0 <= numWays[i] <= 2 * 10^8

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def recover_denominations(numWays: list[int]) -> list[int]:
Java
public List<Integer> recoverDenominations(int[] numWays)

More on the same topics