계속 고민을 해봐도, [[problem:COINS]] 문제 풀이에서 어디가 잘못됐는지를 못찾겠습니다. 일단 예제 입출력은 제대로 되지만, 오답이 계속 나옵니다.
힌트 주실분 안계시나요??

~~~ c++
#include
using namespace std;
#include
#include

#define MAX_COUNT 1000000007

vector coins;
int cache[5000+1][100];

int CountCoins(int sum, int type) {
int& ret = cache[sum][type];

if (sum == 0) return 1;
if (sum < coins.back()) return 0;
if (sum < 0)  return 0;
if (ret != 0) return ret;

for (int i=type; i < coins.size(); ++i)  {
    if (sum >= coins[i]) {
        ret += CountCoins(sum-coins[i], i);
    }
}

if (ret > MAX_COUNT) {
    ret %= MAX_COUNT;
}

return ret;

}

// 환전 금액 (1 <= M <= 5000)
// 동전 종류의 개수 (1 <= C <= 100)

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

for (int n=0; n < num_cases; ++n) {

    // cache 초기화
    fill_n(cache[0], 5001*100, 0);

    // 동전 총합, 코인 개수
    int sum, ncoin;
    cin >> sum >> ncoin;

    // 동전 종류 벡터 생성
    for (int i=0; i<ncoin; i++) {
        int temp;
        cin >> temp;
        coins.push_back(temp);
    }

    // 코인을 정렬
    sort(coins.begin(), coins.end(), greater<int>());
    if (CountCoins(sum, 0) > MAX_COUNT)
        cout << CountCoins(sum, 0) % MAX_COUNT << endl;
    else
        cout << CountCoins(sum, 0) << endl;

    // 초기화
    coins.clear();
}

return 0;

}
~~~