Imagine it like a tree....

let's say we have n = 25 and c = [1,2,3]

we can break it down from 25 into 3 branches by:

25 = 1 + f(24)

25 = 2 + f(23)

25 = 3 + f(22)

each of these scenarios also branch off:

f(24) = 1 + f(23)

f(24) = 2 + f(22)

f(24) = 3 + f(21)

f(23) = 1 + f(22)

f(23) = 2 + f(21)

f(23) = 3 + f(20)

f(22) = 1 + f(21)

f(22) = 2 + f(20)

f(22) = 3 + f(19)

As you keep on propagating... all of the permutations that end up negative are invalid combinations. all of the permutations that end up exactly at 0 are good combinations.

this is a simplistic approach but it's not correct. Because it doesn't differentiate between... [2,2,5] and [5,2,2]. To get only unique combinations you need to remove 1 element from the C set everytime you iterate.

so... it'll look like this (in pseudo code).

static long getWays(long n, long[] c) {
		if (n < 0) {
			return 0;
		}
		if (n == 0) {
			return 1;
		}
		if (CacheValuePopulated(n)){
        return CacheValue(n);
        }
        
		long sum = 0;
		for (int i = 0; i < c.length; i++) {
			long target = n - c[i];
			long[] subc = subArrayOfCFrom(i to end);
			long result = getWays(target, subc);
			if (result > 0) {
				saveResultToYourCache(result);
			}
			sum += result;
		}
		return sum;
	}

Finally... what made the cache problematic was that you can't just save values for any given n.  You have to save values for n BASED on the C subArray you used to calculate it.

Since the problem states that all values of c are unique, I used the first element of the c subarray as a key which pointed to its own n+1 array.

So for example, the cache could differentiate between running (5, [1,2,3]) and (5, [2,3])

f(5,[1,2,3]) = 4 (1,1,1,1,1), (1,1,1,2), (1,1,3), (2, 3) f(5,[2,3]) = 1 (2,3)

I hope this helps everyone. I didn't want to give the full answer away. Good luck!