Help with approach

#1

code: https://ide.codingblocks.com/s/420130

problem: https://leetcode.com/problems/coin-change-2/

please tell what is wrong with my approach

#2

for a simple test case like:
5
[1,2,5]
you are getting 9 instead of 4 coz your coe is counting the prmutations too for cases like 1,2,2 or 1,1,1,2
you can see this simple approach:

public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1,0);
        dp[0] = 1;
        for(int coin : coins)
            for(int i = 1; i <= amount; i++)
                if(i>=coin) dp[i] += dp[i-coin];
        return dp[amount];
    }
};
#3

oh okay but how do I do it top down

#4 
 public:
     int change(int amount, vector<int>& coins) {
        return change(amount, coins, 0);
    }
    
    int change(int amount, vector<int>& coins, int i) {
      if (amount < 0) return 0; // if amount is negative by which means not valid - 0
      if (amount == 0) return 1; // we found exact change
      if (i == coins.length && amount > 0) return 0; // means coins over and n>0 so no solution
      return change(amount - coins[i], coins, i) + change(amount, coins, i + 1); // include + exclude
    }