LeetCode 题解工作台
硬币面值还原
给你一个 从 1 开始计数 的整数数组 numWays ，其中 numWays[i] 表示使用某些 固定 面值的硬币（每种面值可以使用无限次）凑出总金额 i 的方法数。每种面值都是一个 正整数 ，并且其值 最多 为 numWays.length 。 然而，具体的硬币面值已经 丢失 。你的任务是还原出…
2
题型
0
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个 从 1 开始计数 的整数数组 numWays，其中 numWays[i] 表示使用某些 固定 面值的硬币（每种面值可以使用无限次）凑出总金额 i 的方法数。每种面值都是一个 正整数 ，并且其值 最多 为 numWays.length。
然而，具体的硬币面值已经 丢失 。你的任务是还原出可能生成这个 numWays 数组的面值集合。
返回一个按从小到大顺序排列的数组，其中包含所有可能的 唯一 整数面值。
如果不存在这样的集合，返回一个 空 数组。
示例 1：
输入： numWays = [0,1,0,2,0,3,0,4,0,5]
输出： [2,4,6]
解释：
| 金额 | 方法数 | 解释 |
|---|---|---|
| 1 | 0 | 无法用硬币凑出总金额 1。 |
| 2 | 1 | 唯一的方法是 [2]。 |
| 3 | 0 | 无法用硬币凑出总金额 3。 |
| 4 | 2 | 可以用 [2, 2] 或 [4]。 |
| 5 | 0 | 无法用硬币凑出总金额 5。 |
| 6 | 3 | 可以用 [2, 2, 2]、[2, 4] 或 [6]。 |
| 7 | 0 | 无法用硬币凑出总金额 7。 |
| 8 | 4 | 可以用 [2, 2, 2, 2]、[2, 2, 4]、[2, 6] 或 [4, 4]。 |
| 9 | 0 | 无法用硬币凑出总金额 9。 |
| 10 | 5 | 可以用 [2, 2, 2, 2, 2]、[2, 2, 2, 4]、[2, 4, 4]、[2, 2, 6] 或 [4, 6]。 |
示例 2：
输入： numWays = [1,2,2,3,4]
输出： [1,2,5]
解释：
| 金额 | 方法数 | 解释 |
|---|---|---|
| 1 | 1 | 唯一的方法是 [1]。 |
| 2 | 2 | 可以用 [1, 1] 或 [2]。 |
| 3 | 2 | 可以用 [1, 1, 1] 或 [1, 2]。 |
| 4 | 3 | 可以用 [1, 1, 1, 1]、[1, 1, 2] 或 [2, 2]。 |
| 5 | 4 | 可以用 [1, 1, 1, 1, 1]、[1, 1, 1, 2]、[1, 2, 2] 或 [5]。 |
示例 3：
输入： numWays = [1,2,3,4,15]
输出： []
解释：
没有任何面值集合可以生成该数组。
提示：
1 <= numWays.length <= 1000 <= numWays[i] <= 2 * 108
解题思路
方法一
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | and space complexity depend on the DP verification process, which iteratively checks combinations for each candidate denomination against the numWays array, potentially up to O(n^2) in the worst case for array length n. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for recognition that numWays[c] == 1 indicates a base denomination.
- question_mark
Check if candidate denominations are verified via DP rather than guessed.
- question_mark
Evaluate if solution maintains correctness when multiple valid sets exist.
常见陷阱
外企场景- error
Assuming denominations can be any value without checking DP consistency.
- error
Overlooking that multiples of smaller coins influence subsequent numWays counts.
- error
Failing to return a sorted unique array, breaking problem constraints.
进阶变体
外企场景- arrow_right_alt
Recover denominations when numWays array is 0-indexed instead of 1-indexed.
- arrow_right_alt
Determine denominations for numWays arrays allowing limited coin counts per denomination.
- arrow_right_alt
Compute the minimum subset of denominations generating the same numWays pattern.