Solution Coin Change

Denominations: {1,2,3}
Total amount: 5
Output: 5
Explanation: There are five ways to make the change for '5', here are those ways:
  1. {1,1,1,1,1} 
  2. {1,1,1,2} 
  3. {1,2,2}
  4. {1,1,3}
  5. {2,3}

for each coin 'c' 
  create a new set which includes one quantity of coin 'c' if it does not exceed 'T', and 
     recursively call to process all coins 
  create a new set without coin 'c', and recursively call to process the remaining coins 
return the count of sets who have a sum equal to 'T'

class Solution {

  public int countChange(int[] denominations, int total) {
    return this.countChangeRecursive(denominations, total, 0);
  }

  private int countChangeRecursive(
    int[] denominations,
    int total,
    int currentIndex
  ) {
    // basic checks
    if (total == 0) return 1;

    if (
      denominations.length == 0 || currentIndex >= denominations.length
    ) return 0;

    // recursive call after selecting the coin at the currentIndex
    // if the coin at currentIndex exceeds the total, we shouldn't process this
    int sum1 = 0;
    if (denominations[currentIndex] <= total) sum1 = countChangeRecursive(
      denominations,
      total - denominations[currentIndex],
      currentIndex
    );

    // recursive call after excluding the coin at the currentIndex
    int sum2 = countChangeRecursive(denominations, total, currentIndex + 1);

    return sum1 + sum2;
  }

  public static void main(String[] args) {
    Solution cc = new Solution();
    int[] denominations = { 1, 2, 3 };
    System.out.println(cc.countChange(denominations, 5));
  }
}

class Solution {

  public int countChange(int[] denominations, int total) {
    Integer[][] dp = new Integer[denominations.length][total + 1];
    return this.countChangeRecursive(dp, denominations, total, 0);
  }

  private int countChangeRecursive(
    Integer[][] dp,
    int[] denominations,
    int total,
    int currentIndex
  ) {
    // base checks
    if (total == 0) return 1;

    if (
      denominations.length == 0 || currentIndex >= denominations.length
    ) return 0;

    // if we have already processed a similar sub-problem, return the result from memory
    if (dp[currentIndex][total] != null) return dp[currentIndex][total];

    // recursive call after selecting the coin at the currentIndex
    // if the number at currentIndex exceeds the total, we shouldn't process this
    int sum1 = 0;
    if (denominations[currentIndex] <= total) sum1 = countChangeRecursive(
      dp,
      denominations,
      total - denominations[currentIndex],
      currentIndex
    );

    // recursive call after excluding the number at the currentIndex
    int sum2 = countChangeRecursive(dp, denominations, total, currentIndex + 1);

    dp[currentIndex][total] = sum1 + sum2;
    return dp[currentIndex][total];
  }

  public static void main(String[] args) {
    Solution cc = new Solution();
    int[] denominations = { 1, 2, 3 };
    System.out.println(cc.countChange(denominations, 5));
  }
}

    dp[index][t] = dp[index-1][t] + dp[index][t-denominations[index]]

    Denominations: [1, 2, 3]  
    Total: 5 

class Solution {

  public int countChange(int[] denominations, int total) {
    int n = denominations.length;
    int[][] dp = new int[n][total + 1];

    // populate the total=0 columns, as we will always have an empty set for zero total
    for(int i=0; i < n; i++)
      dp[i][0] = 1;
    
    // process all sub-arrays for all capacities
    for(int i=0; i < n; i++) {
      for(int t=1; t <= total; t++) {
        if(i > 0)
          dp[i][t] = dp[i-1][t];
        if(t >= denominations[i])
          dp[i][t] += dp[i][t-denominations[i]];
      }
    }

    // total combinations will be at the bottom-right corner.
    return dp[n-1][total];
  }

  public static void main(String[] args) {
    Solution cc = new Solution();
    int[] denominations = {1, 2, 3};
    System.out.println(cc.countChange(denominations, 5));
  }
}

I'm working on the problem **Solution Coin Change** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Explain the optimal approach to **Solution Coin Change** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

I'll paste my solution to **Solution Coin Change**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Give me 2 problems that use the SAME underlying pattern as **Solution Coin Change**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.