Coin Change II (Count the Ways)
Medium About 20 min Free, no account needed
How many coin combinations make the amount?
The brief
Given denominations coins and an amount, count the combinations (order
does not matter) that sum to amount.
The obvious approach enumerates combinations recursively, exponential. The hidden
test counts the ways to make 5,000 from [1, 2, 5], which an exponential
enumeration will never finish. You need to count each combination exactly once
(not once per ordering) without re-exploring the same subproblem; an
O(amount * coins) solution clears the bar.
Starter code
using System;
public class Solution
{
// TODO: return the number of coin combinations summing to amount (order ignored).
public long ChangeWays(int[] coins, int amount)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
Related guides
What it practices
- Dynamic programming
- Define subproblems and a recurrence, then reuse solved subproblems instead of recomputing them.
Related katas
- Coin Change (Fewest Coins) Medium Free The fewest coins that make the amount, or -1.
- Decode Ways Medium Free How many letter strings could this digit string encode?
- House Robber II (Circular Street) Medium Free The street is a circle now - the first and last houses are neighbors.
- Longest Increasing Subsequence Medium Free Length of the longest strictly increasing subsequence - faster than the quadratic DP.