Coin Change II is one of the most important Counting Dynamic Programming interview questions.

You are given:

coins[]
amount 

Goal:

Find the total number of combinations that make up the given amount.

Important:

You have unlimited copies of every coin. 

Unlike Coin Change I:

Find Minimum Coins 

Coin Change II asks:

Count Total Ways 

Example

amount = 5
coins = [1,2,5] 

Output:

4

Explanation:

5
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 

Total Ways:

4 

Key Observation

For every coin:

Pick coin or Skip coin

Since coins can be reused:

Pick → Stay on same coinSkip → Move to next coin

Recurrence:

dp[i][amount] = pick + skip 

Approach 1 : Memoization

Explanation

For every coin:

1. Use current coin.
2. Skip current coin.
3. Count both possibilities.
4. Store results.
5. Reuse computations.

Approach 2 : Tabulation

Explanation

State:

dp[i][j] = Ways to make amount j using first i coins 

Transition:

dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]] 

Meaning:

Skip Coin + Pick Coin Again 

Dry Run

Input:

amount = 5coins = [1,2,5]

Ways:

5
2+2+1
2+1+1+1
1+1+1+1+1 

Answer:

4 

Approach 3 : Space Optimized DP

Explanation

Store only:

One DP Array 

Process coins one by one.

This avoids counting duplicate combinations.

Practice

MemoizationTime Complexity: O(n × amount)
Space Complexity: O(n × amount)

Tabulation
Time Complexity: O(n × amount)
Space Complexity: O(n × amount)

Space Optimized DP
Time Complexity: O(n × amount)
Space Complexity: O(amount)

Pick coin again or Skip coin 

Pick stays on same coin.