We know a particle moves two units to the right with probability $p$, or $1$ unit to the left with probability $q$, hence $(p+q=1)$.
$$q_k=P\left(S_n=0\mid S_0=k\right)$$
We are asked to find the general and exact solution.
I found the difference equation: $q_k=qq_\left(k-1\right)+pq_\left(k+2\right) $
And then I found the general solution:$$ q_k=A\cdot 1+B\left(\frac{-1}{2}-\sqrt{\frac14+\frac qp}\right)^k+C\left(\frac{-1}{2}+\sqrt{\frac14+\frac qp}\right)^k$$
However, to find the exact solution, I don't know how to solve for $A, B$ & $C$. I tried assuming $q_0=1$, which lets $A+B+C=1$, but that's not enough. Any hint would be greatly appreciated!
The first problem is your definition of $(q_k)_k$. One should consider $q_k=\mathbb P(\text{hits}\ 0\mid S_0=k)$, hence $q_0=1$. The second thing to realize is that there are several regimes.
Assume first that $2p\gt q$. The drift of the random walk is positive hence $S_n\to+\infty$ almost surely. Furthermore, since the only negative jump is $-1$, to hit $0$ starting from $k\geqslant1$, one must hit $k-1$ starting from $k$, then hit $k-1$ starting from $k$, and so on until one hits $0$ starting from $1$. In other words $q_k=q_1^k$ for every $k\geqslant0$.
Now the usual one-step recursion yields $q_k=pq_{k+2}+qq_{k-1}$ for every $k\geqslant1$, hence $q_1^k=pq_1^{k+2}+qq_1^{k-1}$, that is, $q_1$ solves $$ r=pr^3+q. $$ The roots are $\{-s,t,1\}$ with $0\lt t\lt1\lt s$, namely, $$ s=\tfrac12+\tfrac12\sqrt{1+4q/p},\qquad t=-\tfrac12+\tfrac12\sqrt{1+4q/p}. $$ Since $q_k\to0$ when $k\to+\infty$, the only option which is non absurd is that $q_1=t$, hence $q_k=t^k$ for every $k\geqslant0$.
To compute $q_k$ for $k\leqslant-1$, one adopts the same strategy since $q_k=pq_{k+2}+qq_{k-1}$ for every $k\leqslant-1$, where one already knows $q_0=1$ and $q_1=t$. A priori, $(q_k)_{k\leqslant0}$ is a linear combination of the sequences with general terms $1$, $(-s)^k$ and $t^k$. Since $q_k$ should stay bounded when $k\to-\infty$, there is no term in $t^k$, hence there exists some $A$ in $[0,1]$ such that, for every $k\leqslant0$, $q_k=1-A+A(-s)^k$. The recursion for $k=-1$ implies that $1-A+A(-s)^{-1}=pt+q(1-A+A(-s)^{-2})$, which yields $A$, hence $(q_k)_{k\leqslant-1}$.
The case $2p=q$ is singular since the random walk is recurrent hence $q_k=1$ for every $k$.
When $2p\lt q$, $S_n\to-\infty$ almost surely hence $q_k=1$ for every $k\geqslant1$. For $k\leqslant-1$, now $q_k\to0$ when $k\to-\infty$ hence the roots $1$ and $t$ do not contribute, that is, $q_k=(-s)^k$ for every $k\leqslant0$.