void exchange(int target, int *units, int length, int *res);
void dfs(int target, int *units, int length, int *res);
int main(int argc, char *argv[]) {
int coins[] = {1, 2, 5};
for (int target = 1; target <= 20; target++) {
int result = 0;
exchange(target, coins, sizeof coins / sizeof coins[0], &result);
printf("target: %3d\t-> %3d\n", target, result);
}
}
void exchange(int target, int *units, int length, int *res) {
if (0 == target) {
return;
}
dfs(target, units, length, res);
}
void dfs(int target, int *units, int length, int *res) {
if (0 == target) {
*res = *res + 1;
return;
}
for (int i = 0; i < length; i++) {
if (units[i] > target) {
continue;
}
dfs(target - units[i], units, length, res);
}
}
需要对结果去重 |