title: How to find ALL Eulerian paths in directed graph
body: <p>I have a directed graph and I want to find all existing eulerian paths (in my graph I actually know  that those will be circuits). </p>
  
  <p>I have done some research so I can use for example Hierholzer's algorithm as in here: <a href="http://stones333.blogspot.co.uk/2013/11/find-eulerian-path-in-directed-graph.html" rel="nofollow">http://stones333.blogspot.co.uk/2013/11/find-eulerian-path-in-directed-graph.html</a> to find a path from given node but this algorithm returns only one path I believe.</p>
  
  <p>My idea to solve this is to have an algorithm that will return ALL existing Eulerian paths / circuits starting from given node. Then I will run this algorithms for all nodes and get the results. This will have n^2 or n^3 complexity which is great.</p>
  
  <p>So my question is if there is an algorithm that will find all Eulerian paths / circuits in directed graph from given node? Or maybe someone knows another solution to my problem.</p>
  
  <p>EDIT:
  after Gassa comment I think that the solution with Euler paths might be an overkill for my problem. Problem is as follows: for given n we create a pairs of integers which sum is &lt;= n. For those pairs find all paths that connects all of the pairs such that second value of previous pair equals to the first value from next pair (like domino). </p>
  
  <p>Example: n = 2, then available pairs = {(0,0), (0,1),(1,0),(1,1),(2,0),(0,2)}. One of the valid chains = (0,0)=>(0,1)=>(1,1)=> (1,0)=>(0,2)=>(2,0). I preferred algorithm using graphs because for example (0,0) might not be valid sometimes, but let's say it is valid for the sake of this question. Brute force solution to this problem is to of course create all permutations of available pairs and then see if they are valid but this is obviously O(n!) complex. I am pretty sure this could be done in some "smart" way.</p>