Inverse coin change

Array Dynamic Programming

51.5% acceptance

Feb 25, 2026

163

You are given a 1-indexed integer array numWays, where numWays[i] represents the number of ways to select a total amount i using infinite supply of the coin denominations. Recover the set of denominations. Return sorted array of unique denominations. If no such set exists, return empty array.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_coins(num_ways: Vec<i32>) -> Vec<i32> {
    let n = num_ways.len();
    // Standard coin-change DP: dp[i] = number of ways to make amount i.
    // dp[0] = 1. For each coin c: dp[i] += dp[i-c].
    // To recover coins: dp starts as num_ways (1-indexed).
    // At amount i (1-indexed), if numWays[i-1] > 0 and we subtract contributions from known coins,
    // the remainder must be explained by a new coin of denomination i.
    // number of new ways from coin i for amount i = dp[i-i] = dp[0] = 1 (using coin i once).
    // Subtract contributions of already-found coins from dp[i]:
    // remaining = dp[i] - sum over c in coins where c < i: dp[i-c]
    // If remaining == 1: coin i is a denomination.
    // If remaining == 0: no new coin.
    // If remaining < 0 or remaining > 1: invalid.

    let mut dp = vec![0i64; n + 1];
    dp[0] = 1;
    let mut coins = vec![];

    for i in 1..=n {
      // dp[i] is num_ways[i-1] (the "target")
      let target = num_ways[i - 1] as i64;
      // Compute contribution from already-known coins
      let known_contribution = dp[i];
      let remainder = target - known_contribution;
      if remainder < 0 {
        return vec![];
      } else if remainder == 0 {
        // No new coin at this denomination; dp[i] = target
        dp[i] = target;
        // Update future dp values with existing coins contribution is already embedded
      } else if remainder == 1 {
        // New coin of denomination i
        coins.push(i as i32);
        dp[i] = target;
        // Update dp for future amounts
        for j in (i + 1)..=n {
          dp[j] += dp[j - i];
        }
      } else {
        return vec![];
      }
    }

    // Verify the dp matches num_ways exactly
    for i in 1..=n {
      if dp[i] != num_ways[i - 1] as i64 {
        return vec![];
      }
    }

    coins
  }
}