#include<iostream>
using namespace std;
#define LEN 3

int a[] = {1, 2, 5};
int remain(int i){
    int total = 0;
    for(int j=LEN-1;j>i;j--)
        total += a[j];
    return total;
}
long dfs(int total, int i){
    if(i>=3){
        if(total==0)
            return 1;
        return 0;
    }
     
    long res = 0;
    for(int num=1;total-a[i]*num>=remain(i);++num){
        res += dfs(total-num*a[i], i+1);    
    }

    return res;
}
int main(){
    printf("%ld\n", dfs(100, 0));

}

------解决方案--------------------
按照面值从大到小处理，一张张累加，剩下的能被最小面值整除，则是一种组合。
Java code

public class PayType {

    private static int count=0;
    private static int coins[]={1,2,5};
    public static void main(String[] args) {
        int amount=1*100;
        int coinsCount[]=new int[coins.length];
        //先每种至少一张
        for(int i=coinsCount.length-1;i>=0;i--)
        {
            amount-=coins[i];
            coinsCount[i]=1;
        }
        //从最大开始付
        pay(amount,coinsCount.length-1,coinsCount);
        System.out.println("count:"+count);
    }

    private static void print(int coinsCount[])
    {
        count++;
        String str="";
        int total=0;
        for(int i=coinsCount.length-1;i>=0;i--)
        {
            if(i==coinsCount.length-1)
                str+=coins[i]+"*"+coinsCount[i];
            else
                str+="+"+coins[i]+"*"+coinsCount[i];
            total+=coins[i]*coinsCount[i];
        }
        System.out.println(str+"="+total);
    }

    private static void pay(int amount,int coinIdx,int srcCoinsCount[])
    {
        int coin=coins[coinIdx];
        int[] coinsCount=new int[srcCoinsCount.length];
        for(int i=0;i<coinsCount.length;i++)
        {
            coinsCount[i]=srcCoinsCount[i];
        }
        //如果是最小一种
        if(coinIdx==0)
        {
            //整除，则合适
            if(amount%coin==0)
            {
                coinsCount[coinIdx]+=amount/coin;
                print(coinsCount);
            }
            return;
        }
        if(amount>=coin)
        {
            //用下一种面值付
            pay(amount,coinIdx-1,coinsCount);
            //继续用当前面值付
            coinsCount[coinIdx]++;
            amount-=coin;
            pay(amount,coinIdx,coinsCount);
        }
        //不够，则用下一种面值付
        else
        {
            pay(amount,coinIdx-1,coinsCount);
        }
            
    }
}