Untitled

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<vector<int>> dp(coins.size()+1, vector<int>(amount+1, 0));
        sort(coins.begin(), coins.end());
        // for each coin, # ways to sum to 0 is 1
        for(int c=0;c<=coins.size();c++) {
            dp[c][0] = 1;
        }
        for(int c=coins.size()-1;c>=0;c--) {
            for(int a=0;a<=amount;a++) {
                if(a-coins[c]>=0) {
                    dp[c][a] = dp[c+1][a];
                    dp[c][a] += dp[c][a-coins[c]];
                }
            }
        }

        return dp[0][amount];
    }
};