Coin Combinations Count

Problem Statement

Given a set of coin denominations and a total sum, write a function to find the total number of unique ways to make that sum using any number of coins from the given denominations. Each type of coin can be used an unlimited number of times.

Examples

Example 1:

Input: total = 6, coins = [1, 3, 4]
Output: 6
Explanation: The six ways to make 6 are:
6 = 4 + 1 + 1
6 = 3 + 3
6 = 3 + 1 + 1 + 1
6 = 1 + 1 + 1 + 1 + 1 + 1
6 = 4 + 2 (not valid, since 2 is not in coins)
6 = 3 + 3 (already counted)

Example 2:

Input: total = 4, coins = [2, 5]
Output: 0
Explanation: No combination of coins 2 and 5 can sum up to 4.

Example 3:

Input: total = 8, coins = [2, 4]
Output: 3
Explanation: The combinations are:
8 = 4 + 4
8 = 2 + 2 + 4
8 = 2 + 2 + 2 + 2

Constraints

• 0 ≤ total ≤ 4000
• 1 ≤ coin value ≤ 4000
• Number of coin types ≤ 300
• Result fits within a 32-bit signed integer