>>472 枝狩り一切無し
#include<stdio.h>
void coin_num_check(int num[], int tmp[], int kind_num){
    int num_total=0, tmp_total=0, i;
    for(i=0;i<kind_num;i++){
        num_total+=num[i];
        tmp_total+=tmp[i];
    }
    if(num_total>tmp_total || num_total==0) for(i=0;i<kind_num;i++) num[i]=tmp[i];
}
int coin_check(int kind[], int num[], int tmp[], int kind_num, int kind_index, int value){
    int i;
    if(kind_index>=kind_num) return 0;
    for(i=0;kind[kind_index]*i<=value;i++){
        tmp[kind_index]=i;
        if(kind[kind_index]*i==value) coin_num_check(num, tmp, kind_num);
        coin_check(kind, num, tmp, kind_num, kind_index+1, value-kind[kind_index]*i);
    }
    return 1;
}
int main(void){
    int kind[]={25,10,1}, num[sizeof(kind)/sizeof(kind[0])]={0}, tmp[sizeof(kind)/sizeof(kind[0])]={0}, i, x, total=0;
    printf("Input value : ");
    scanf("%d", &x);
    coin_check(kind, num, tmp, sizeof(kind)/sizeof(kind[0]), 0, x);
    for(i=0;i<sizeof(kind)/sizeof(kind[0]);i++){
        if(num[i]>0) printf("%5d : %d\n", kind[i], num[i]);
        total+=num[i];
    }
    printf("\nTotal : %d\n", total);
    return 0;
}