기본 완전탐색에서 dp를 추가했는데 이상한 답만 뜨네요... 일주일째 고민중인데도 모르겠습니다...ㅠㅠㅠ

코인이 큰 순서대로 남은 돈(left)에서 빼고 재귀를 계속 호출해 0이 나오면 방법을 하나 찾았다고 보고 리턴합니다.
dp는 남은 돈 기준으로 하여 150원이 남았다고 하면 이를 cache 배열에서 찾아 이전정보가 있으면 그를 리턴합니다.

이하는 코드입니다. 도와주시면 감사하겠습니다....ㅠㅠ

#include <stdio.h>
#include <string.h>
int coin[110];
int m, c;
int cache[5010];

int howMany(int forward,int left) {
    int ans = 0;
    if (left == 0) return 1;
    for (int i = forward; i >=0 ; i--) {
        if (left >= coin[i]) {
            if (cache[left] != -1) return cache[left];
            left = left - coin[i];
            ans += howMany(i, left);
            cache[left] = ans;
            left = left + coin[i];
        }
    }
    return ans;
}

int main() {
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; i++) {
        memset(cache, -1, sizeof(cache));
        scanf("%d%d", &m, &c);
        for (int j = 0; j < c; j++) {
            scanf("%d", &coin[j]);
        }
        printf("%d\n", howMany(c-1,m));
    }
    return 0;
}