Here is a derivation of a really explicit formula for $C(n)$, which I've below called $p_{123}(n)$.
Let $p_{23}(n)$ denote the number of partitions of $n$ into $2$s and $3$s. If you use $k$ $2$s, then you must make up $n-2k$ using $3$s, so we must have $n - 2k \equiv 0 \pmod 3$, and also $2k\le n$. So,
If $n \equiv 0 \pmod 3$, then $k \equiv 0 \pmod 3$, so every $k = 3l$ from $l=0$ to $l=\lfloor n/6 \rfloor$ works.
If $n = 6m$ or $n=6m + 3$ then $p_{23}(n) = m+1$.
If $n \equiv 1 \pmod 3$, then $k \equiv 2 \pmod 3$, so every $k = 3l+2$ from $l=0$ to $l=\lfloor (n-4)/6 \rfloor$ works.
If $n = 6m+1$ then $p_{23}(n) = m$ and if $n=6m+4$ then $p_{23}(n) = m+1$.
If $n \equiv 2 \pmod 3$, then $k \equiv 1 \mod 3$, so every $k = 3l+1$ from $l=0$ to $\lfloor (n-2)/6 \rfloor$ works.
If $n = 6m+2$ or $n=6m+5$ then $p_{23}(n) = m+1$.
So now we have a closed-form expression for $p_{23}(n)$.
Let $p_{123}(n)$ denote the number of ways of writing $n$ as a sum of $1$s, $2$s and $3$s. Then, by summing over the number of $1$s we use, $ p_{123}(n) = \sum_{i=0}^{n} p_{23}(n-i) = \sum_{i=0}^{n} p_{23}(i).$
Now the sum over $p_{23}(i)$ is easy to calculate for each consecutive bunch of 6 numbers: $p_{23}(6r) + p_{23}(6r+1) + p_{23}(6r+2) + p_{23}(6r+3) + p_{23}(6r+4) + p_{23}(6r+5)$ $ = (r+1) + r + (r+1) + (r+1) + (r+1) + (r+1)$ $ = 6r + 5 $
So if $\lfloor n/6 \rfloor = m$, then
$\begin{align} p_{123}(n) &= \sum_{i=0}^{n} p_{23}(i) \\ &= \sum_{i=0}^{6m-1} p_{23}(i) + \sum_{i=6m}^{n} p_{23}(i)\\ &= \sum_{r=0}^{m-1} (6r+5) + \sum_{i=6m}^{n} p_{23}(i) \\ &= 6\frac{(m-1)m}{2} + 5m + \sum_{i=6m}^{n} p_{23}(i) \\ &= 3m^2 + 2m + \sum_{i=6m}^{n} p_{23}(i) \end{align}$
Specifically,
If $n = 6m$ then $p_{123}(n) = (3m^2 + 2m) + (m+1) = 3m^2 + 3m + 1$
If $n = 6m+1$ then $p_{123}(n) = (3m^2 + 3m + 1) + m = 3m^2 + 4m + 1$
If $n = 6m+2$ then $p_{123}(n) = (3m^2 + 4m + 1) + (m+1) = 3m^2 + 5m + 2$
If $n = 6m+3$ then $p_{123}(n) = (3m^2 + 5m + 2) + (m+1) = 3m^2 + 6m + 3$
If $n = 6m+4$ then $p_{123}(n) = (3m^2 + 6m + 3) + (m+1) = 3m^2 + 7m + 4$
If $n = 6m+5$ then $p_{123}(n) = (3m^2 + 7m + 4) + (m+1) = 3m^2 + 8m + 5.$
This can be written as $\frac{n^2}{12} + \frac{n}{2} + c$ where $c$ is $1$, $\frac5{12}$, $\frac23$, $\frac34$, $\frac23$, or $\frac5{12}$ depending on whether $n$ modulo $6$ is $0$, $1$, $2$, $3$, $4$ or $5$ respectively.
Although all this looks very ad hoc, I believe it can be generalised to any general set $\{a_1, a_2, \dots, a_k\}$. You'll still have to take cases and evaluate sums about $k$ times, and you'll get a polynomial of degree $k-1$, and (I guess) at most $\mathrm{lcm}(a_1, \dots, a_k)$ cases. I don't think this is necessarily messier to do by hand than actually carrying out the generating functions -> partial fractions -> … approach to completion.