From 2030aed15343b830f6a68e4746f42a921fa3d917 Mon Sep 17 00:00:00 2001 From: Charles Cabergs Date: Thu, 14 Jan 2021 12:22:37 +0100 Subject: problem 31 in c --- c/031-coin_sums.c | 45 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 45 insertions(+) create mode 100644 c/031-coin_sums.c (limited to 'c') diff --git a/c/031-coin_sums.c b/c/031-coin_sums.c new file mode 100644 index 0000000..2aff382 --- /dev/null +++ b/c/031-coin_sums.c @@ -0,0 +1,45 @@ +/* +* Coin sums +* Problem 31 +* +* In the United Kingdom the currency is made up of pound (£) and pence (p). There are eight coins in general circulation: +* 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), and £2 (200p). +* It is possible to make £2 in the following way: +* 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p +* How many different ways can £2 be made using any number of coins? +*/ + +#include + +static int count = 0; +static int coins[] = {200, 100, 50, 20, 10, 5, 2, 1}; + +void solve(int curr_pos) +{ + static int curr[2048] = {0}; + + int sum = 0; + for (int i = 0; i < curr_pos; i++) + sum += curr[i]; + if (sum == 200) + { + count++; + return; + } + if (sum > 200) + return; + for (unsigned int i = 0; i < sizeof(coins) / sizeof(coins[0]); i++) + { + if (curr_pos != 0 && curr[curr_pos - 1] < coins[i]) + continue; + curr[curr_pos] = coins[i]; + solve(curr_pos + 1); + } +} + +int main(void) +{ + solve(0); + printf("%d\n", count); + return 0; +} -- cgit