题目描述
题目描述
题解
题解
提交记录
提交记录
中等

给你一个 从 1 开始计数 的整数数组 numWays,其中 numWays[i] 表示使用某些 固定 面值的硬币(每种面值可以使用无限次)凑出总金额 i 的方法数。每种面值都是一个 正整数 ,并且其值 最多 numWays.length

然而,具体的硬币面值已经 丢失 。你的任务是还原出可能生成这个 numWays 数组的面值集合。

返回一个按从小到大顺序排列的数组,其中包含所有可能的 唯一 整数面值。

如果不存在这样的集合,返回一个 空 数组。

 

示例 1:

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

输出: [2,4,6]

解释:

金额方法数解释
10无法用硬币凑出总金额 1。
21唯一的方法是 [2]
30无法用硬币凑出总金额 3。
42可以用 [2, 2][4]
50无法用硬币凑出总金额 5。
63可以用 [2, 2, 2][2, 4][6]
70无法用硬币凑出总金额 7。
84可以用 [2, 2, 2, 2][2, 2, 4][2, 6][4, 4]
90无法用硬币凑出总金额 9。
105可以用 [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]

解释:

金额方法数解释
11唯一的方法是 [1]
22可以用 [1, 1][2]
32可以用 [1, 1, 1][1, 2]
43可以用 [1, 1, 1, 1][1, 1, 2][2, 2]
54可以用 [1, 1, 1, 1, 1][1, 1, 1, 2][1, 2, 2][5]

示例 3:

输入: numWays = [1,2,3,4,15]

输出: []

解释:

没有任何面值集合可以生成该数组。

 

提示:

  • 1 <= numWays.length <= 100
  • 0 <= numWays[i] <= 2 * 108
 
代码
代码
测试用例
测试用例
测试结果
测试结果