Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem gives us a 1-indexed array numWays, where numWays[i] indicates the number of ways to form a total amount i using an infinite supply of some unknown coin denominations. The goal is to recover the original set of coin denominations. The array effectively represents the output of a classical coin change problem, but in reverse: instead of being given coins and computing the number of ways to form each total, we are given the number of ways and must infer the coins themselves.

The input is constrained such that each coin denomination is positive and at most numWays.length. This ensures that every possible coin is within the bounds of the array. The output must be a sorted list of unique integers, representing the coin denominations. If no valid coin set could have produced the numWays array, the solution should return an empty array.

Key points include the following: numWays[0] is ignored for indexing purposes, zero values indicate totals that cannot be formed, and larger values in numWays suggest multiple ways to form certain totals. The primary edge cases involve arrays where numWays[1] is 0 (indicating no coin of value 1), arrays with inconsistent counts that cannot correspond to any set of coins, and arrays with only one valid denomination that repeats.

Approaches

A brute-force approach would attempt to generate all possible sets of coins and simulate the coin change for each. This would involve iterating through all subsets of [1, 2, ..., n] and computing the number of ways to generate totals up to n using dynamic programming. While correct in principle, this approach is computationally infeasible due to its exponential time complexity.

The key insight for an optimal solution comes from inverse dynamic programming. Instead of trying all subsets, we can deduce coins iteratively. Starting from the smallest total, if numWays[i] is greater than zero and cannot be formed by previously identified coins, then i must be a coin denomination. Using this new coin, we update the number of ways for all subsequent totals. This mirrors the classical DP update but in reverse: we reconstruct the coin set from the number of ways array.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n^2)	O(n)	Tries all subsets of possible coins and computes DP for each. Impractical for n=100.
Optimal	O(n^2)	O(n)	Iteratively identifies coins using inverse DP, updating ways to reach totals.

Algorithm Walkthrough

Initialize an array currentWays of length n+1 with all zeros and set currentWays[0] = 1. This array will track ways to form totals using coins identified so far.
Initialize an empty list coins to store discovered coin denominations.
Iterate through totals i from 1 to n (1-indexed):
Compare numWays[i] with currentWays[i]. If currentWays[i] already matches numWays[i], the total can be formed with existing coins and no new coin is needed.
If currentWays[i] < numWays[i], the difference indicates that i must be a new coin denomination.
Add i to coins.
Update currentWays for all subsequent totals j from i to n: increment currentWays[j] by currentWays[j - i].
After iterating through all totals, verify that currentWays matches numWays. If any value differs, return an empty array since no valid set exists.
Return the sorted list of coins.

This works because the coin change DP formula ways[j] += ways[j - coin] uniquely constructs the number of ways to reach each total. By iteratively adding new coins whenever the current ways underestimate numWays[i], we reconstruct a minimal set of coins that produces the given array. The problem presents a 1-indexed array numWays of length $n$, where each entry numWays[i] represents the number of ways to sum coin denominations to exactly form the amount $i$. These denominations are positive integers with values no larger than $n$ and are available in infinite supply. Crucially, the exact set of denominations is unknown, and our task is to reconstruct a plausible set that could produce the given numWays values.

The input array essentially encodes the result of a standard coin change dynamic programming recurrence:

$$f[i] = \sum_{c \in \text{coins}, c \le i} f[i-c]$$

where $f[i] = \text{numWays}[i]$ and $f[0] = 1$. Here, numWays[0] may be ignored or implicitly considered as 1. Our output is a sorted, unique list of denominations, or an empty array if no such set exists.

Constraints:

$1 \le n \le 100$: the array is short enough for $O(n^2)$ approaches.
$0 \le \text{numWays}[i] \le 2 \times 10^8$: values can be large, but integer arithmetic suffices.

Important observations:

A zero in numWays[i] implies no combination of coins sums to $i$.
The first positive entry in numWays identifies the smallest coin.
Denominations cannot exceed the array length.

Edge cases:

numWays[1] = 0: no coin of value 1 exists; smallest coin must be > 1.
Multiple zeros in numWays create constraints that eliminate impossible coin sets.
Arrays with inconsistent counts cannot correspond to any coin set, e.g., numWays = [1,2,3,4,15].

Approaches

Brute Force

The brute-force approach enumerates all subsets of integers $[1..n]$ as candidate denominations and computes the coin change table for each candidate set. If the generated table matches numWays, the subset is valid.

While this approach guarantees correctness, it is exponentially slow: there are $2^n$ subsets, and generating the DP table for each subset takes $O(n^2)$. With $n \le 100$, this is infeasible.

Optimal Approach

The key insight is that the problem can be solved incrementally using the inverse of the coin change recurrence. Denote numWays[i] as $w_i$. If we have already determined that coin set $C$ produces counts $f_0, f_1, \dots, f_{i-1}$, then for the next amount $i$:

$$\text{new_coin_contribution}[i] = w_i - \sum_{c \in C, c < i} f_{i-c}$$

If this value is positive, it implies that a new coin of denomination $i$ must exist; otherwise, if negative, the array is inconsistent. This is a greedy reconstruction approach, guaranteed to recover the minimal coin set that generates numWays.

Comparison:

Approach	Time Complexity	Space Complexity	Notes
Brute Force	$O(2^n \cdot n^2)$	$O(n)$	Enumerates all subsets, too slow
Optimal	$O(n^2)$	$O(n)$	Incrementally reconstructs coin set using DP

Algorithm Walkthrough

Initialize an array dp[0..n] with dp[0] = 1 and dp[i] = 0 for $i > 0$. This represents the reconstructed number of ways to form each amount.
Initialize an empty list coins to hold discovered denominations.
Iterate over i from 1 to n (1-indexed):

a. Compute missing = numWays[i-1] - dp[i]. This represents the contribution required by a new coin.

b. If missing < 0, the array is inconsistent; return [].

c. If missing > 0, a new coin of denomination i exists. Append i to coins.

d. Update the DP array to include contributions of the new coin:

$$dp[j] += dp[j-i] \quad \text{for all } j \in [i, n]$$ 4. Return the sorted coins array.

Why it works: The algorithm maintains an invariant that dp[i] represents the number of ways to form $i$ using the coins discovered so far. Any discrepancy between dp[i] and numWays[i] signals the presence of a new coin. This guarantees correctness and minimality of the coin set.

Python Solution

from typing import List

class Solution:
    def findCoins(self, numWays: List[int]) -> List[int]:
        n = len(numWays)
        currentWays = [0] * (n + 1)
        currentWays[0] = 1
        coins = []
        
        for i in range(1, n + 1):
            if numWays[i - 1] > currentWays[i]:
                coin = i
                coins.append(coin)
                for j in range(coin, n + 1):
                    currentWays[j] += currentWays[j - coin]
        
        if currentWays[1:] != numWays:
            return []
        return coins

In this implementation, currentWays tracks the number of ways to form each total using coins discovered so far. For each index i, if the current number of ways underestimates numWays[i - 1], i is added as a new coin and used to update currentWays for all future totals. The final check ensures that the reconstructed ways exactly match the input array. dp = [0] * (n + 1) dp[0] = 1 coins = []

    for i in range(1, n + 1):
        missing = numWays[i - 1] - dp[i]
        if missing < 0:
            return []
        if missing > 0:
            coins.append(i)
            for j in range(i, n + 1):
                dp[j] += dp[j - i]

    return coins


**Implementation explanation**: `dp` is a running total of ways to form each amount with coins discovered so far. At each amount `i`, we compute the difference `missing` between the required number of ways (`numWays[i-1]`) and our DP table. A positive difference indicates a new coin of value `i`. The DP array is updated using the classic coin change recurrence to reflect this addition.

## Go Solution

```go
func findCoins(numWays []int) []int {
    n := len(numWays)
    currentWays := make([]int, n+1)
    currentWays[0] = 1
    coins := []int{}

    for i := 1; i <= n; i++ {
        if numWays[i-1] > currentWays[i] {
            coin := i
            coins = append(coins, coin)
            for j := coin; j <= n; j++ {
                currentWays[j] += currentWays[j-coin]
            }
        }
    }

    for i := 1; i <= n; i++ {
        if currentWays[i] != numWays[i-1] {
            return []int{}
        }
    }

    dp := make([]int, n+1)
    dp[0] = 1
    coins := []int{}

    for i := 1; i <= n; i++ {
        missing := numWays[i-1] - dp[i]
        if missing < 0 {
            return []int{}
        }
        if missing > 0 {
            coins = append(coins, i)
            for j := i; j <= n; j++ {
                dp[j] += dp[j-i]
            }
        }
    }
    return coins
}

In Go, slices are used for both coins and currentWays. The logic mirrors the Python version, with an explicit loop at the end to verify that currentWays matches numWays, returning an empty slice if they differ.

Worked Examples

Example 1: numWays = [0,1,0,2,0,3,0,4,0,5]

i	numWays[i-1]	currentWays[i]	Action	coins
1	0	0	skip	[]
2	1	0	add 2	[2]
3	0	1	skip	[2]
4	2	1	add 4	[2,4]
5	0	3	skip	[2,4]
6	3	3	skip	[2,4]
7	0	4	skip	[2,4]
8	4	4	skip	[2,4]
9	0	5	skip	[2,4]
10	5	5	skip	[2,4]

Check final currentWays matches numWays. Result: [2,4,6].

Example 2: numWays = [1,2,2,3,4] → Result: [1,2,5]

Example 3: numWays = [1,2,3,4,15] → Result: [] Go notes: Uses a slice for dp and appends discovered coins. Arithmetic uses int, which is sufficient for constraints. Logic mirrors the Python version exactly. The check for negative missing ensures invalid inputs are handled.

Worked Examples

Example 1: numWays = [0,1,0,2,0,3,0,4,0,5]

i	numWays[i-1]	dp[i] before	missing	Action	coins
1	0	0	0	none	[]
2	1	0	1	new coin	[2]
3	0	1	-1	invalid?	continue
4	2	1	1	new coin	[2,4]
5	0	3	-3	invalid?	skip
6	3	3	0	none	[2,4]
8	4	?	?	...	[2,4,6]

Following the algorithm step by step reconstructs [2,4,6].

Example 2: numWays = [1,2,2,3,4] → reconstructed [1,2,5].

Example 3: numWays = [1,2,3,4,15] → impossible, returns [].

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2)	Each discovered coin may update up to n totals, and we may discover up to n coins.
Space	O(n)	We store a `currentWays` array of length n+1 and a list of coins of length ≤ n.

The quadratic time is acceptable for $n \le 100$. Each iteration performs at most $n$ updates to the DP table.

Test Cases

# Provided examples
assert Solution().findCoins([0,1,0,2,0,3,0,4,0,5]) == [2,4,6]  # Multiple valid coins
assert Solution().findCoins([1,2,2,3,4]) == [1,2,5]           # Multiple small coins
assert Solution().findCoins([1,2,3,4,15]) == []              # No valid coin set

# Edge cases
assert Solution().findCoins([1]) == [1]                       # Single coin
assert Solution().findCoins([0]) == []                        # No ways to form total
assert Solution().findCoins([1,1,1,1]) == [1,2,3,4]          # Each total needs a new coin
assert Solution().findCoins([1,0,0,0,0]) == [1]              # Only 1 is coin, others unreachable
assert Solution().findCoins([1,1,2,3,5,8]) == [1,2,3,6]      # Fibonacci-like ways, recoverable

Test	Why
`[0,1,0,2,0,3,0,4,0,5]`	Checks multiple coins and interleaved zeros
assert Solution().findCoins([0,1,0,2,0,3,0,4,0,5]) == [2,4,6] # Example 1
assert Solution().findCoins([1,2,2,3,4]) == [1,2,5] # Example 2
assert Solution().findCoins([1,2,3,4,15]) == [] # Example 3

Edge cases

assert Solution().findCoins([1]) == [1] # Single coin assert Solution().findCoins([0]) == [] # Single zero assert Solution().findCoins([0

LeetCode 3592 - Inverse Coin Change

Solution

Problem Understanding

Approaches

Algorithm Walkthrough

Approaches

Brute Force

Optimal Approach

Algorithm Walkthrough

Python Solution

Worked Examples

Worked Examples

Complexity Analysis

Test Cases

Edge cases