Recover Coin Denominations from Combination Counts

# Recover Coin Denominations from Combination Counts You are given `numWays` of length `N`. Its entry `numWays[a - 1]` gives the number of ways to make amount `a`, for every amount from one through `N`, using an unlimited supply of coins from one fixed set of denominations. Every denomination is a positive integer at most `N`. Ways count combinations of coins: changing the order in which the same coins are selected does not create another way. Recover a denomination set that reproduces all the supplied counts. Return its distinct values in increasing order. If no such set exists, return an empty array. ### C++ Interface ```cpp class Solution { public: vector<int> findCoins(vector<int>& numWays); }; ``` ### Examples **Example 1** ```text numWays = [1,1,2,2,2,4] Output: [1,3,6] ``` For amounts one through six, the combinations are: - `1`: `[1]`. - `2`: `[1,1]`. - `3`: `[1,1,1]` or `[3]`. - `4`: `[1,1,1,1]` or `[1,3]`. - `5`: `[1,1,1,1,1]` or `[1,1,3]`. - `6`: `[1,1,1,1,1,1]`, `[1,1,1,3]`, `[3,3]`, or `[6]`. These counts are exactly `[1,1,2,2,2,4]`. **Example 2** ```text numWays = [0,1,1,1,3] Output: [] ``` Amount one excludes denomination one. The counts for amounts two and three then require denominations two and three. Those coins provide only `[2,3]` for amount five. Including denomination five could add `[5]`, but this still gives only two combinations, not the required three. ### Constraints - `1 <= numWays.length <= 100`. - `0 <= numWays[i] <= 200000000`. - Every recovered denomination must lie between one and `numWays.length`, inclusive. - Each denomination has an unlimited supply; the returned list is sorted and contains no duplicates. ### Clarifying Questions - Does the input include an entry for amount zero? No. Vector index zero describes amount one. - Are permutations such as `[1,2]` and `[2,1]` different ways? No. They are the same combination. - May a denomination exceed the largest reported amount? No. The source restricts denominations to at most `N`. - Can the supplied counts be inconsistent? Yes; return an empty array if no set reproduces them all. - Should the function return just any subset whose small-amount counts match? No. Every reported amount must match. ### What a Strong Answer Covers - Exact reconstruction or rejection against all amounts one through `N`. - Unlimited reuse of each denomination while counting unordered combinations. - Increasing, duplicate-free returned denominations within the allowed range. - Safe count arithmetic for inconsistent inputs and counts up to 200000000, with `N <= 100`. ### Follow-up Questions - How would counting ordered coin sequences instead of combinations change the meaning of a reported count? Give a small example. - What returned array is required when every reported positive amount has count zero? ```hint Compare with smaller denominations Consider candidate denominations from one upward. Maintain combination counts using those already recovered. At amount c, denominations larger than c cannot contribute, and adding denomination c introduces exactly one additional way to make c: the single coin c. Use this forced choice to decide whether c belongs in the set, then update combination counts forward for unlimited use. ```