Count Unordered Combinations of Unlimited Coins

Given an array coins of positive coin denominations and a nonnegative integer target, return the number of distinct combinations of coins whose total value is exactly target. You may use each denomination an unlimited number of times.

The order of coins within a combination does not matter. For example, [1, 2, 1] and [2, 1, 1] represent the same combination.

Function Contract

Implement count_coin_combinations(coins, target) -> int.

Return the exact combination count. Do not return the combinations themselves and do not apply a modulus.

Constraints and Clarifications

The following bounds and duplicate-denomination rule are explicit practice assumptions:

• 0 <= len(coins) <= 100.
• Every denomination is an integer from 1 through 10000.
• Denominations are distinct, and the input order may be arbitrary.
• 0 <= target <= 100.
• The count fits a signed 32-bit integer under these bounds.
• There is one way to make a target of zero: choose no coins.
• With no denominations, a positive target has zero combinations.

Examples

coins = [1, 2, 3]
target = 4
Output: 4

The combinations are four 1 coins; two 1 coins and one 2; two 2 coins; and one 1 plus one 3.

coins = [2]
target = 3
Output: 0