COINS문제를 풀고 있습니다.

다음과 같은 과정으로 문제를 풀었는데요,

• 동적 할당하여 배열에 동전 값을 입력
• 입력받은 동전을 큰 순서부터 내림차순으로 정렬 (이 때, 계산하고자 하는 금액보다 큰 금액은 제거하여 정렬)
• 큰 동전부터 0개 ~ 셀 수 있는 가장 큰 경우까지 반복
• 각각의 경우에서 재귀함수를 호출해 더 작은 동전의 경우를 계산
• 가장 작은 동전의 경우에서는 count값 추가.
• MAX 보다 작은 나머지를 반환

하는 재귀 알고리즘을 사용하였습니다.
그런데 계속하여 마지막 경우 (총액이 1278) 에서 계산 시간이 엄청 길어지네요. 물론 시간 초과로 오답이 나왔습니다.

어떻게 하면 시간을 단축하여 개선할 수 있을까요?

고수님들의 도움 부탁드립니다.

#include <stdio.h>
#include <stdlib.h>

#define MAX 1000000007

int check2(int amount, int coins[], int idx, int size){

    unsigned int count = 0;
    int val = amount/coins[idx];
    
    for(int i=0; i<=val; i++){
        if(size-1 != idx){
            count += check2(amount-i*coins[idx], coins, idx+1, size);
        }else{
            return ++count;         
        }
    }
    return count%MAX;
}

int* sort(int* arr, int* size, int amount){

    for(int i=0; i<*size; i++){
        for(int j=i+1; j<*size; j++){
            if(arr[i]<arr[j]){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }

    // 총 금액보다 큰 단위의 동전 제거
    while(arr[0] > amount){
        arr = &arr[1];
        *size = *size -1;
    }

    return arr;
}

int main(){

    int T = 0;
    scanf("%d", &T);

    for(int i=0;i<T;i++){

        int M, C, count = 0;
        scanf("%d %d", &M, &C);

        int* coins = (int*)malloc(sizeof(int) * C);

        for(int j=0; j< C; j++){
            scanf("%d", &coins[j]);
        }

        coins = sort(coins, &C, M);

        count = check2(M, coins, 0, C);

        printf("%d\n", count);
        
        coins = NULL;
        free(coins);
    }
    
    return 0;
}