Infinite Coins

vector<int> coins;
vector<vector<tuple<int, int, int, int>>> memo;

vector<tuple<int, int, int, int>> ways(int money) {
    if (money < 0) return {};
    if (money == 0) return vector<tuple<int, int, int, int>>(1, make_tuple(0, 0, 0, 0));

    vector<tuple<int, int, int, int>> &ans = memo[money];
    if (!ans.empty()) return ans;

    for (int coin: coins) {
        vector<tuple<int, int, int, int>> aux = ways(money - coin);
        for (auto [quarters, dimes, nickels, pennies]: aux) {
            int dq = coin == 25 ? 1 : 0;
            int dd = coin == 10 ? 1 : 0;
            int dn = coin == 5 ? 1 : 0;
            int dp = coin == 1 ? 1 : 0;
            ans.emplace_back(quarters + dq, dimes + dd, nickels + dn, pennies + dp);
        }
    }

    return ans;
}

int main() {
    int money; cin >> money;

    memo.assign(money + 1, vector<tuple<int, int, int, int>>());

    vector<tuple<int, int, int, int>> ans = ways(money);
    for (auto [quartes, dimes, nickels, pennies]: ans)
        cout << quarters << " " << dimes << " " << nickels << " " << pennies << "\n";
}