돈 계산

#include <stdio.h>
#include <stdlib.h>
 
void pick(int money[], int itemSize,  int* bucket, int bucketSize, int k)
{
    int i, lastIndex, smallest, item, total = 0;
 
    if (k == 0)
    {
        for (i = 0; i < bucketSize; i++)
            total += money[bucket[i]];
 
        if (total == (bucketSize * 1000))
            for (i = 0; i < bucketSize; i++)
            {
                if (bucket[i] == 0)
                    continue;
 
                printf("%d ", money[bucket[i]]);
            }
        else
            return;
 
        printf("\n");
        return;
    }
 
    lastIndex = bucketSize - k - 1;
 
    if (bucketSize == k)
        smallest = 0;
    else
        smallest = bucket[lastIndex];
 
    for (item = smallest; item < itemSize; item++)
    {
        bucket[lastIndex + 1] = item;
        pick(money, itemSize, bucket, bucketSize, k - 1);
    }
}
 
int main(void)
{
    int items[] = { 0, 1000, 5000, 10000 };
    int* bucket;
    int money, n;
 
    scanf("%d", &money);
    n = money / 1000;
 
    bucket = (int *)malloc(sizeof(int) * n);
    pick(items, 4, bucket, n, n);
}

 

결과: