# Count all Hamiltonian paths in a given directed graph

Given a directed graph of **N** vertices valued from **0** to **N – 1** and array **graph[]** of size **K** represents the Adjacency List of the given graph, the task is to count all Hamiltonian Paths in it which start at the **0 ^{th}** vertex and end at the

**(N – 1)**vertex.

^{th}**Note: **Hamiltonian path is defined as the path which visits every vertex of the graph exactly once.

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

**Examples:**

Input:N = 4, K = 6, graph[][] = {{1, 2}, {1, 3}, {2, 3}, {3, 2}, {2, 4}, {3, 4}}Output:2Explanation:

The paths below shown are 1 -> 3 -> 2 -> 4 and 1 -> 2 -> 3 -> 4 starts at 1 and ends at 4 and are called Hamiltonian paths.

Input:N = 2, K = 1, graph[][] = {{1, 2}}Output:1

**Approach:** The given problem can be solved by using Bitmasking with Dynamic Programming, and iterate over all subsets of the given vertices represented by an **N** size mask and check if there exists a Hamiltonian Path that starts at the **0 ^{th}** vertex and ends at

**(N – 1)**vertex and count all such paths. Let’s say for a graph having

^{th}**N**vertices

**S**represents a bitmask where

**S = 0**to

**S = (1 << N) -1**and

**dp[i][S]**represents the number of paths that visits every vertex in the mask

**S**and ends at

**i**then the valid recurrence will be given as

**dp[i][S] = ∑ dp[j][S XOR 2**where

^{i}] where j ∈ S and there is an edge from j to i**S XOR 2**

^{i }^{ }represents the subset which does not have the

**ith**vertex in it and there must be an edge from

**j**to

**i**. Follow the steps below to solve the given problem:

- Initialize a 2-D array
**dp[N][2**with^{N}]**0**and set**dp[0][1]**as**1**. - Iterate over the range from
**[2, 2**using the variable^{N}– 1]**i**and check for the mask having all bits set in it.- Iterate over the range from
**[0, N)**using the variable**end**and traverse over all bits of the current mask and assume each bit as the ending bit.- Initialize the variable
**prev**as**i – (1 << end).** - Iterate over the range
**[0, size)**where**size**is the size of the array**graph[end]**using the variable**it**and traverse over the adjacent vertices of the current ending bit and update the**dp[][]**array like this**dp[end][i] += dp[it][prev].**

- Initialize the variable

- Iterate over the range from
- After performing the above steps, print the value of
**dp[N-1][2**as the answer.^{N}– 1]

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find all possible paths` `void` `findAllPaths(` ` ` `int` `N, vector<vector<` `int` `> >& graph)` `{` ` ` `// Initialize a dp array` ` ` `int` `dp[N][(1 << N)];` ` ` `// Initialize it with 0` ` ` `memset` `(dp, 0, ` `sizeof` `dp);` ` ` `// Initialize for the first vertex` ` ` `dp[0][1] = 1;` ` ` `// Iterate over all the masks` ` ` `for` `(` `int` `i = 2; i < (1 << N); i++) {` ` ` `// If the first vertex is absent` ` ` `if` `((i & (1 << 0)) == 0)` ` ` `continue` `;` ` ` `// Only consider the full subsets` ` ` `if` `((i & (1 << (N - 1)))` ` ` `&& i != ((1 << N) - 1))` ` ` `continue` `;` ` ` `// Choose the end city` ` ` `for` `(` `int` `end = 0; end < N; end++) {` ` ` `// If this city is not in the subset` ` ` `if` `(i & (1 << end) == 0)` ` ` `continue` `;` ` ` `// Set without the end city` ` ` `int` `prev = i - (1 << end);` ` ` `// Check for the adjacent cities` ` ` `for` `(` `int` `it : graph[end]) {` ` ` `if` `((i & (1 << it))) {` ` ` `dp[end][i] += dp[it][prev];` ` ` `}` ` ` `}` ` ` `}` ` ` `}` ` ` `// Print the answer` ` ` `cout << dp[N - 1][(1 << N) - 1];` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `N = 4;` ` ` `vector<vector<` `int` `> > graph(N);` ` ` `graph[1].push_back(0);` ` ` `graph[2].push_back(0);` ` ` `graph[2].push_back(1);` ` ` `graph[1].push_back(2);` ` ` `graph[3].push_back(1);` ` ` `graph[3].push_back(2);` ` ` `findAllPaths(N, graph);` ` ` `return` `0;` `}` |

## Python3

`# python program for the above approach` `# Function to find all possible paths` `def` `findAllPaths(N, graph):` ` ` `# Initialize a dp array` ` ` `# Initialize it with 0` ` ` `dp ` `=` `[[` `0` `for` `_ ` `in` `range` `(` `1` `<< N)] ` `for` `_ ` `in` `range` `(N)]` ` ` `# Initialize for the first vertex` ` ` `dp[` `0` `][` `1` `] ` `=` `1` ` ` `# Iterate over all the masks` ` ` `for` `i ` `in` `range` `(` `2` `, (` `1` `<< N)):` ` ` `# If the first vertex is absent` ` ` `if` `((i & (` `1` `<< ` `0` `)) ` `=` `=` `0` `):` ` ` `continue` ` ` `# Only consider the full subsets` ` ` `if` `((i & (` `1` `<< (N ` `-` `1` `)))` `and` `i !` `=` `((` `1` `<< N) ` `-` `1` `)):` ` ` `continue` ` ` `# Choose the end city` ` ` `for` `end ` `in` `range` `(` `0` `, N):` ` ` `# If this city is not in the subset` ` ` `if` `(i & (` `1` `<< end) ` `=` `=` `0` `):` ` ` `continue` ` ` `# Set without the end city` ` ` `prev ` `=` `i ` `-` `(` `1` `<< end)` ` ` `# Check for the adjacent cities` ` ` `for` `it ` `in` `graph[end]:` ` ` `if` `((i & (` `1` `<< it))):` ` ` `dp[end][i] ` `+` `=` `dp[it][prev]` ` ` `# Print the answer` ` ` `print` `(dp[N ` `-` `1` `][(` `1` `<< N) ` `-` `1` `])` `# Driver Code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` `N ` `=` `4` ` ` `graph ` `=` `[[] ` `for` `_ ` `in` `range` `(N)]` ` ` `graph[` `1` `].append(` `0` `)` ` ` `graph[` `2` `].append(` `0` `)` ` ` `graph[` `2` `].append(` `1` `)` ` ` `graph[` `1` `].append(` `2` `)` ` ` `graph[` `3` `].append(` `1` `)` ` ` `graph[` `3` `].append(` `2` `)` ` ` `findAllPaths(N, graph)` ` ` `# This code is contributed by rakeshsahni` |

## Javascript

`<script>` `// Javascript program for the above approach` `// Function to find all possible paths` `function` `findAllPaths(N, graph) {` ` ` `// Initialize a dp array` ` ` `let dp = ` `new` `Array(N).fill(0).map(() => ` `new` `Array(1 << N).fill(0));` ` ` `// Initialize for the first vertex` ` ` `dp[0][1] = 1;` ` ` `// Iterate over all the masks` ` ` `for` `(let i = 2; i < 1 << N; i++) {` ` ` `// If the first vertex is absent` ` ` `if` `((i & (1 << 0)) == 0) ` `continue` `;` ` ` `// Only consider the full subsets` ` ` `if` `(i & (1 << (N - 1)) && i != (1 << N) - 1) ` `continue` `;` ` ` `// Choose the end city` ` ` `for` `(let end = 0; end < N; end++) {` ` ` `// If this city is not in the subset` ` ` `if` `(i & (1 << end == 0)) ` `continue` `;` ` ` `// Set without the end city` ` ` `let prev = i - (1 << end);` ` ` `// Check for the adjacent cities` ` ` `for` `(let it of graph[end]) {` ` ` `if` `(i & (1 << it)) {` ` ` `dp[end][i] += dp[it][prev];` ` ` `}` ` ` `}` ` ` `}` ` ` `}` ` ` `// Prlet the answer` ` ` `document.write(dp[N - 1][(1 << N) - 1]);` `}` `// Driver Code` `let N = 4;` `let graph = ` `new` `Array(N).fill(0).map(() => []);` `graph[1].push(0);` `graph[2].push(0);` `graph[2].push(1);` `graph[1].push(2);` `graph[3].push(1);` `graph[3].push(2);` `findAllPaths(N, graph);` `// This code is contributed by gfgking.` `</script>` |

**Output:**

2

**Time Complexity:** O(N*2^{N})**Auxiliary Space:** O(1)