Find no of acyclic paths of any length in a directed graph from a single source given that every node has at most 4 in/out degree

Question

let A,B,C be nodes of directed graph with edges A->B,B->A,A->C,C->A,B->C,C->B then no of paths will be 5 that is A,A->B,A->C,A->B->C,A->C->B

If i apply dfs and increase counter for every node i visit, it wont find all paths for example if it finds A,A->B,A->B->C then after backtrack it wont traverse A->C and further A->C->B because C and B are marked as visited.

So i modified the dfs where i unmarked the visited node when algorithm backtracks to its parent.

Procedure dfs(arr,s,vis):  #s is source node
  vis[s]=True              #mark as visited
  count+=1                 #no of paths
  for all i adjacent to s:
    if not vis[i]:
        dfs(arr,i,vis)
  vis[s]=False             #mark visited as false again(modification)

After modification, algorithm gives correct result but the time complexity goes exponential.

Is there any optimized way to do it? Note that i am developing a game and in my specific scenario

• In-degree/Out-degree of any node is at most 4
• In-degree/Out-degree of source node is at most 2

Any idea?