Fastest algorithm to find all the possible paths of length $n$ from a give node in a directed graph? I am trying to find the fastest algorithm to find all the possible paths of length $N$ from a given node in a directed graph. 

My solution is to do a modification of breadth first search from the given node for $N$ iteration. Its time complexity is around $\theta(V+E)$. But the problem is $|V|$ &amp; $|E|$ becomes exponential because as long as there is an edge, the same node can be visited again.

Can there be a solution of this problem with polynomial time complexity? It seems this problem has optimal substructure solution. Is there any solution using dynamic approach?
This problem is NP-hard, since the Hamiltonian Path problem is a special case of this problem where we set N=n and check whether the answer is strictly greater than zero.

This problem is actually #P-hard wich is believed to be strictly harder than NP.

The version of the problem where you only look for the existence of such a path is called the longest path problem. A well-known problem in theory. It is fixed-parameter tractable when parameterized by the length of the path (check Parameterized Algorithms book by Cygan et al for description and methods).