1 files changed, 45 insertions, 0 deletions
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 <stdio.h>
+
+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;
+}