You are given a 1-indexed integer array numWays, where numWays[i] represents the number of ways to select a total amount i using an infinite supply of some fixed coin denominations. Each denomination is a positive integer with value at most numWays.length.
However, the exact coin denominations have been lost. Your task is to recover the set of denominations that could have resulted in the given numWays array.
Return a sorted array containing unique integers which represents this set of denominations.
If no such set exists, return an empty array.
Example 1:
Input: numWays = [0,1,0,2,0,3,0,4,0,5]
Output: [2,4,6]
Explanation:
| Amount | Number of ways | Explanation |
|---|---|---|
| 1 | 0 | There is no way to select coins with total value 1. |
| 2 | 1 | The only way is [2]. |
| 3 | 0 | There is no way to select coins with total value 3. |
| 4 | 2 | The ways are [2, 2] and [4]. |
| 5 | 0 | There is no way to select coins with total value 5. |
| 6 | 3 | The ways are [2, 2, 2], [2, 4], and [6]. |
| 7 | 0 | There is no way to select coins with total value 7. |
| 8 | 4 | The ways are [2, 2, 2, 2], [2, 2, 4], [2, 6], and [4, 4]. |
| 9 | 0 | There is no way to select coins with total value 9. |
| 10 | 5 | The ways are [2, 2, 2, 2, 2], [2, 2, 2, 4], [2, 4, 4], [2, 2, 6], and [4, 6]. |
Input: numWays = [1,2,2,3,4]
Output: [1,2,5]
Explanation:
| Amount | Number of ways | Explanation |
|---|---|---|
| 1 | 1 | The only way is [1]. |
| 2 | 2 | The ways are [1, 1] and [2]. |
| 3 | 2 | The ways are [1, 1, 1] and [1, 2]. |
| 4 | 3 | The ways are [1, 1, 1, 1], [1, 1, 2], and [2, 2]. |
| 5 | 4 | The ways are [1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2], and [5]. |
Example 3:
Input: numWays = [1,2,3,4,15]
Output: []
Explanation:
No set of denomination satisfies this array.
Constraints:
1 <= numWays.length <= 1000 <= numWays[i] <= 2 * 108Problem Overview: You are given an array where ways[i] represents the number of ways to form amount i using unlimited coins. The task is to recover the set of coin denominations that would produce exactly this dynamic programming table.
Approach 1: Brute Force Coin Set Search (Exponential Time)
Try every possible subset of coin denominations from 1..n. For each candidate set, recompute the classic coin change DP where dp[i] += dp[i - coin]. If the generated table matches the provided ways array, that set is valid. This method uses a full recomputation for each subset, resulting in O(2^n * n^2) time and O(n) space. It proves the problem is solvable but becomes infeasible even for moderate n.
Approach 2: DP Reconstruction from Ways Array (O(n^2))
The key observation: the standard coin change DP builds values incrementally by processing coins in increasing order. If a denomination c exists, it increases the number of ways for all amounts i ≥ c using dp[i] += dp[i - c]. Start with a fresh DP array where dp[0] = 1 and everything else is 0. Iterate amounts from 1 to n. If the computed dp[i] is smaller than ways[i], that gap must come from introducing a coin of value i. Add i to the coin set and update the DP for all future indices using the classic transition. Continue until the reconstructed DP matches the given array. This simulation runs in O(n^2) time with O(n) space.
The technique relies on the monotonic nature of coin processing: smaller denominations affect more states, so detecting discrepancies early reveals which coin must exist. Each discovered coin triggers a standard unbounded knapsack update across the array.
Implementation closely mirrors the classic dynamic programming formulation of coin change. The only difference is that instead of counting combinations for a target, you reconstruct the coin set that would generate the provided DP table. The input structure behaves like a prefix of the usual DP state array.
This problem combines ideas from array processing and incremental dynamic programming transitions. Careful state comparison between the generated DP and the provided array is the core step.
Recommended for interviews: The DP reconstruction approach. Interviewers expect you to recognize the classic coin change transition and reverse the process. Mentioning the brute force search demonstrates understanding of the search space, but reconstructing coins in O(n^2) time shows strong DP intuition.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Coin Set Search | O(2^n * n^2) | O(n) | Useful only for reasoning or very small inputs |
| DP Reconstruction from Ways Array | O(n^2) | O(n) | General case. Efficiently reconstructs denominations by simulating coin change DP |
Inverse Coin Change| LeetCode contest 455| leetcode 3592 | must do dynamic programming | top DP dsa • Code Thoughts • 2,197 views views
Watch 7 more video solutions →Practice Inverse Coin Change with our built-in code editor and test cases.
Practice on FleetCode