131. Coin Change II — Combination Count
Count different selections of coin counts whose total value equals the amount. Each denomination can be used any number of times.
Changing the order in which the same coins are listed does not create a new combination. Repeated equal denominations describe one coin type in this course.
Example 1
Input
coins=[1,2,5], amount=5
Output
4
Explanation: The multisets are {5}, {2,2,1}, {2,1,1,1}, and {1,1,1,1,1}.
Example 2
Input
coins=[1,2], amount=3
Output
2
Explanation: {1,1,1} and {1,2}; [1,2] and [2,1] are one multiset.
Example 3
Input
coins=[2,2], amount=4
Output
1
Explanation: Both entries name the same type, so only {2,2} is counted.
Example 4
Input
coins=[], amount=0
Output
1
Explanation: The empty combination is the counting identity.
Constraints
0 <= coins.length <= 1001 <= coins[i] <= 1040 <= amount <= 104- Duplicate denominations are allowed.
Hints
Hint 1
Give each multiset a canonical denomination order so it is constructed once.
Hint 2
Split solutions into zero copies of the current type and at least one copy.
Hint 3
Use coin outside and sums increasing inside; initialize ways[0] to BigInteger.ONE.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Type layers prevent permutation duplicates
[1,2]
3
"2"