forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcoin_change.py
More file actions
39 lines (28 loc) · 902 Bytes
/
coin_change.py
File metadata and controls
39 lines (28 loc) · 902 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
"""
Coin Change (Number of Ways)
Given a value and a set of coin denominations, count how many distinct
combinations of coins sum to the given value.
Reference: https://leetcode.com/problems/coin-change-ii/
Complexity:
Time: O(n * m) where n is the value and m is the number of coins
Space: O(n)
"""
from __future__ import annotations
def count(coins: list[int], value: int) -> int:
"""Find the number of coin combinations that add up to value.
Args:
coins: List of coin denominations.
value: Target sum.
Returns:
Number of distinct combinations that sum to value.
Examples:
>>> count([1, 2, 3], 4)
4
>>> count([2, 5, 3, 6], 10)
5
"""
dp_array = [1] + [0] * value
for coin in coins:
for i in range(coin, value + 1):
dp_array[i] += dp_array[i - coin]
return dp_array[value]