Loading
Loading
A self-service kiosk pays refunds in coins and has an unlimited stock of each coin type it holds. The operators want to know how much flexibility the kiosk has for a given refund.
Given the refund amount and the coin values, return the number of different collections of coins that add up to the amount. Collections are unordered: 2 + 1 and 1 + 2 are the same collection. Paying 0 has exactly one collection, the empty one.
amount = 5, coins = [1, 2, 5]start: ways = [1, 0, 0, 0, 0, 0]only 0 is payable with no coinswith 1s: [1, 1, 1, 1, 1, 1]one way for every amountwith 2s: [1, 1, 2, 2, 3, 3]ways[a] += ways[a - 2]with 5s: [1, 1, 2, 2, 3, 4]ways[5] += ways[0]4Sign in to keep a note here. It is free, and nobody else can see it.
Sign inExample 1
Sign in to open hints.
Struggling is where the learning happens. Open this once you have genuinely tried, or once the hints have run out.
O(amount × k) time · O(amount) space
Input. Run your code to watch it work on this input, one line at a time.
Running code is turned off on this deployment. You can still read the problem, write code, use hints and the visualizer.
Tab moves focus out of the editor. Press Ctrl+M to let Tab indent instead.
No results yet
Run your code against the sample tests, or submit to run the full suite.
5; 2 + 2 + 1; 2 + 1 + 1 + 1; 1 + 1 + 1 + 1 + 1.
Example 2
Only even amounts can be paid in 2-coins.
Example 3
The empty collection is the one way to pay nothing.