Funcia
Lv.2dp

Coin Change Ways

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Given distinct coin denominations coins (unlimited supply of each) and an amount, return the number of ways to make exactly amount, where the order of coins does not matter (1 + 2 and 2 + 1 are the same way). Return it modulo 1,000,000,0071{,}000{,}000{,}007; return 0 if it is impossible.

Examples

coinsamountresult
[1, 2, 5]54
[2]30
[3, 7]212

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(coins: int[], amount: int) → int

Constraints

  • 1≤1 \le coins.length ≤50\le 50, distinct values, 1≤1 \le coins[i] ≤100,000\le 100{,}000
  • 1≤1 \le amount ≤100,000\le 100{,}000

Expected complexity

Time
O(C * A)
Space
O(A)

Examples

coinsamountExpected
[1,2,5]54
[2]30
[3,7]212

Hint

Hint

ways[0] = 1; for each coin c (outer loop) and each amount a from c up, ways[a] += ways[a - c]. Looping over coins on the outside is what stops 1+2 and 2+1 from being counted twice. Summing every possible count of each coin is O(A2)O(A^2) for small coins and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4010verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.