Find the number of ways a number can be expressed as a sum of primes?

**Test Case:** Number 7 can be wrtten as **2+2+3, 2+3+2, 2+5, 3+2+2, 5+2** in **5 ways**.

This is last year's Nutanix interview question which I came across while sitting for campus placements. It's been one year since I saw the question. Still couldn't figure out how to solve the problem. Any help is really appreciated!!

Can you please share the constraints?

Sorry I don't remember the actual constraints. Let us assume 1 <= N <= 1000. Since the answer can be very large, let us return answer mod 1000000009. Hope this helps.

Sure. It helps.

What we are doing is iterating over the

lastsummand of $$$i$$$. If the last summand of $$$i$$$ is $$$p$$$, then, the integer becomes $$$(i - p)$$$.Thanks for the help!

How can we solve the problem if we consider combinations instead of permutations. For example 7 can be written as

2+2+3, 2+5in2 ways.Then, we need to introduce another dimension into our DP.

Let $$$f(i, j)$$$ be the number of ways of writing $$$i$$$ where the largest prime is the $$$j$$$ th prime.

There are two options —

$$$f(i, j) = f(i - p_j, j) + f(i, j - 1)$$$

P.S. — This is quite tricky for beginners. The main idea behind finding the state and transition of the DP and ensuring we don't overcount is to create a clear bijection between what we are counting and the DP.

In this case, there is a bijection between a way of writing $$$n$$$ and the largest prime that we have used.

Thanks!! Successfully implemented the idea.

This is a very well known problem. It is called Coin Combinations. You just have to find the primes first. They are the coins here. Then just see Coin Combinations 1 & 2 in this editorial: https://codeforces.com/blog/entry/70018

Thanks for sharing the blog. This has everything that I need.