新手c语言编程穷举问题

Question

有四种面值不一样的货币分别是10元，5元，2元，1元。现在给你一个钱数你能求求它的组成方法都有多少吗？

运行时间尽可能短

Answer 1

问题解决的话，请点下采纳，谢谢

// Q1051673.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"


#include <stdio.h>
#include <string.h>

void solve(int * seed, int nseed, int * cand, int ncand, int target)
{
    if (target == 0)
    {
        for (int i = 0; i < nseed; i++)
        {
            printf("%d ", seed[i]);
        }
        printf("\n");
        return;
    }
    for (int i = 0; i < ncand; i++)
    {
        if (target >= cand[i] && cand[i] <= seed[nseed - 1])
        {
            int * seed1 = new int[nseed + 1];
            memcpy(seed1, seed, nseed * sizeof(int));
            seed1[nseed] = cand[i];
            solve(seed1, nseed + 1, cand, ncand, target - cand[i]);
            delete[] seed1;
        }
    }
}

int main()
{
    int cand[4] = { 10, 5, 2, 1 };
    int target = 25; //钱数
    for (int i = 0; i < 4; i++)
    {
        int * seed = new int[1];
        seed[0] = cand[i];
        solve(seed, 1, cand, 4, target - seed[0]);
        delete[] seed;
    }
}

10 10 5
10 10 2 2 1
10 10 2 1 1 1
10 10 1 1 1 1 1
10 5 5 5
10 5 5 2 2 1
10 5 5 2 1 1 1
10 5 5 1 1 1 1 1
10 5 2 2 2 2 2
10 5 2 2 2 2 1 1
10 5 2 2 2 1 1 1 1
10 5 2 2 1 1 1 1 1 1
10 5 2 1 1 1 1 1 1 1 1
10 5 1 1 1 1 1 1 1 1 1 1
10 2 2 2 2 2 2 2 1
10 2 2 2 2 2 2 1 1 1
10 2 2 2 2 2 1 1 1 1 1
10 2 2 2 2 1 1 1 1 1 1 1
10 2 2 2 1 1 1 1 1 1 1 1 1
10 2 2 1 1 1 1 1 1 1 1 1 1 1
10 2 1 1 1 1 1 1 1 1 1 1 1 1 1
10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 5 5 5 5
5 5 5 5 2 2 1
5 5 5 5 2 1 1 1
5 5 5 5 1 1 1 1 1
5 5 5 2 2 2 2 2
5 5 5 2 2 2 2 1 1
5 5 5 2 2 2 1 1 1 1
5 5 5 2 2 1 1 1 1 1 1
5 5 5 2 1 1 1 1 1 1 1 1
5 5 5 1 1 1 1 1 1 1 1 1 1
5 5 2 2 2 2 2 2 2 1
5 5 2 2 2 2 2 2 1 1 1
5 5 2 2 2 2 2 1 1 1 1 1
5 5 2 2 2 2 1 1 1 1 1 1 1
5 5 2 2 2 1 1 1 1 1 1 1 1 1
5 5 2 2 1 1 1 1 1 1 1 1 1 1 1
5 5 2 1 1 1 1 1 1 1 1 1 1 1 1 1
5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 2 2 2 2 2 2 2 2 2 2
5 2 2 2 2 2 2 2 2 2 1 1
5 2 2 2 2 2 2 2 2 1 1 1 1
5 2 2 2 2 2 2 2 1 1 1 1 1 1
5 2 2 2 2 2 2 1 1 1 1 1 1 1 1
5 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
5 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1
5 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2 2 2 2 1
2 2 2 2 2 2 2 2 2 2 2 1 1 1
2 2 2 2 2 2 2 2 2 2 1 1 1 1 1
2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Press any key to continue . . .