3592. Inverse Coin Change Medium
1/**
2 * [3592] Inverse Coin Change
3 *
4 * 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.
5 * 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.
6 * Return a sorted array containing unique integers which represents this set of denominations.
7 * If no such set exists, return an empty array.
8 *
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">numWays = [0,1,0,2,0,3,0,4,0,5]</span>
12 * Output: <span class="example-io">[2,4,6]</span>
13 * Explanation:
14 * <table style="border: 1px solid black;">
15 * <tbody>
16 * <tr>
17 * <th style="border: 1px solid black;">Amount</th>
18 * <th style="border: 1px solid black;">Number of ways</th>
19 * <th style="border: 1px solid black;">Explanation</th>
20 * </tr>
21 * <tr>
22 * <td style="border: 1px solid black;">1</td>
23 * <td style="border: 1px solid black;">0</td>
24 * <td style="border: 1px solid black;">There is no way to select coins with total value 1.</td>
25 * </tr>
26 * <tr>
27 * <td style="border: 1px solid black;">2</td>
28 * <td style="border: 1px solid black;">1</td>
29 * <td style="border: 1px solid black;">The only way is [2].</td>
30 * </tr>
31 * <tr>
32 * <td style="border: 1px solid black;">3</td>
33 * <td style="border: 1px solid black;">0</td>
34 * <td style="border: 1px solid black;">There is no way to select coins with total value 3.</td>
35 * </tr>
36 * <tr>
37 * <td style="border: 1px solid black;">4</td>
38 * <td style="border: 1px solid black;">2</td>
39 * <td style="border: 1px solid black;">The ways are [2, 2] and [4].</td>
40 * </tr>
41 * <tr>
42 * <td style="border: 1px solid black;">5</td>
43 * <td style="border: 1px solid black;">0</td>
44 * <td style="border: 1px solid black;">There is no way to select coins with total value 5.</td>
45 * </tr>
46 * <tr>
47 * <td style="border: 1px solid black;">6</td>
48 * <td style="border: 1px solid black;">3</td>
49 * <td style="border: 1px solid black;">The ways are [2, 2, 2], [2, 4], and [6].</td>
50 * </tr>
51 * <tr>
52 * <td style="border: 1px solid black;">7</td>
53 * <td style="border: 1px solid black;">0</td>
54 * <td style="border: 1px solid black;">There is no way to select coins with total value 7.</td>
55 * </tr>
56 * <tr>
57 * <td style="border: 1px solid black;">8</td>
58 * <td style="border: 1px solid black;">4</td>
59 * <td style="border: 1px solid black;">The ways are [2, 2, 2, 2], [2, 2, 4], [2, 6], and [4, 4].</td>
60 * </tr>
61 * <tr>
62 * <td style="border: 1px solid black;">9</td>
63 * <td style="border: 1px solid black;">0</td>
64 * <td style="border: 1px solid black;">There is no way to select coins with total value 9.</td>
65 * </tr>
66 * <tr>
67 * <td style="border: 1px solid black;">10</td>
68 * <td style="border: 1px solid black;">5</td>
69 * <td style="border: 1px solid black;">The ways are [2, 2, 2, 2, 2], [2, 2, 2, 4], [2, 4, 4], [2, 2, 6], and [4, 6].</td>
70 * </tr>
71 * </tbody>
72 * </table>
73 * <strong class="example">Example 2:
74 * <div class="example-block">
75 * Input: <span class="example-io">numWays = [1,2,2,3,4]</span>
76 * Output: <span class="example-io">[1,2,5]</span>
77 * Explanation:
78 * <table style="border: 1px solid black;">
79 * <tbody>
80 * <tr>
81 * <th style="border: 1px solid black;">Amount</th>
82 * <th style="border: 1px solid black;">Number of ways</th>
83 * <th style="border: 1px solid black;">Explanation</th>
84 * </tr>
85 * <tr>
86 * <td style="border: 1px solid black;">1</td>
87 * <td style="border: 1px solid black;">1</td>
88 * <td style="border: 1px solid black;">The only way is [1].</td>
89 * </tr>
90 * <tr>
91 * <td style="border: 1px solid black;">2</td>
92 * <td style="border: 1px solid black;">2</td>
93 * <td style="border: 1px solid black;">The ways are [1, 1] and [2].</td>
94 * </tr>
95 * <tr>
96 * <td style="border: 1px solid black;">3</td>
97 * <td style="border: 1px solid black;">2</td>
98 * <td style="border: 1px solid black;">The ways are [1, 1, 1] and [1, 2].</td>
99 * </tr>
100 * <tr>
101 * <td style="border: 1px solid black;">4</td>
102 * <td style="border: 1px solid black;">3</td>
103 * <td style="border: 1px solid black;">The ways are [1, 1, 1, 1], [1, 1, 2], and [2, 2].</td>
104 * </tr>
105 * <tr>
106 * <td style="border: 1px solid black;">5</td>
107 * <td style="border: 1px solid black;">4</td>
108 * <td style="border: 1px solid black;">The ways are [1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2], and [5].</td>
109 * </tr>
110 * </tbody>
111 * </table>
112 * </div>
113 * <strong class="example">Example 3:
114 * <div class="example-block">
115 * Input: <span class="example-io">numWays = [1,2,3,4,15]</span>
116 * Output: <span class="example-io">[]</span>
117 * Explanation:
118 * No set of denomination satisfies this array.
119 * </div>
120 * <table style="border: 1px solid black;">
121 * </table>
122 * </div>
123 *
124 * Constraints:
125 *
126 * 1 <= numWays.length <= 100
127 * 0 <= numWays[i] <= 2 * 10^8
128 *
129 */
130pub struct Solution {}
131
132// problem: https://leetcode.com/problems/inverse-coin-change/
133// discuss: https://leetcode.com/problems/inverse-coin-change/discuss/?currentPage=1&orderBy=most_votes&query=
134
135// submission codes start here
136
137impl Solution {
138 pub fn find_coins(num_ways: Vec<i32>) -> Vec<i32> {
139 vec![]
140 }
141}
142
143// submission codes end
144
145#[cfg(test)]
146mod tests {
147 use super::*;
148
149 #[test]
150 fn test_3592() {
151 }
152}
153Back
© 2026 bowen.ge All Rights Reserved.