What is the correct complexity of All paths from Source to Target DFS solution?
First recall the definition of topological sort: given a DAG (Directed Acyclic Graph) with vertices $1, \dots n$ define the vector $\operatorname{TS}[1, \dots n]$ such that $\operatorname{TS}[1, \dots n]$ is a permutation of $1\, \dots n$ and $i &lt; j$ implies that a path from node $\operatorname{TS}[j]$ to $\operatorname{TS}[i]$ does not exist. This vector can be computed in $\mathcal{O}(n)$ time.

Consider the algorithm exposed in your link, and denote with $T(n)$ the time complexity of that problem for a DAG of size $n$, then it holds:

$$ T(n) = \sum_{i=1}^{n}T(i).$$

Proof: If you call your function on $\operatorname{TS}[i]$ its execution consists of recursively calling that function on the sub-graphs composed of vertices reachable (following a directed path) from $\operatorname{TS}[j]$ such that $(i, j) \in E$. Exploiting the topological sort property it turns out that 

$$\{\text{Vertices Reachable from} \operatorname{TS}[j]\} \subseteq \{\operatorname{TS}[k] \;|\; k = j + 1, \dots n\}.$$

Moreover $(i, j) \in E \implies i &lt; j$, then you are calling the same function on smaller instances of the same problem, satisfying the equation above.

Finally, considering that $T(0) = T(1) = 1$ the complexity is $T(n) = \mathcal{O}(2^n)$ that solves that recursion.