Hamiltonian Path

A Hamiltonian path, is a path in an undirected or directed graph that visits each vertex exactly once. Given an undirected graph the task is to check if a Hamiltonian path is present in it or not.

• Time : O(n!)
• Space : O(n + m)

class Solution {
    vector<vector<int>> adj;
    bool helper(int u, int mask, int target) {
        if(mask == target) return true;
        for(auto& v : adj[u]) {
            if(mask & (1<<v)) continue;
            if(helper(v, mask | 1<<v, target))
                return true;
        }
        return false;
    }
public:
    bool check(int n, int m, vector<vector<int>> Edges) {
        adj = vector<vector<int>>(n);
        for(int i = 0; i < m; i++) {
            int u = Edges[i][0], v = Edges[i][1];
            adj[u-1].push_back(v-1);
            adj[v-1].push_back(u-1);
        }
        for(int i = 0; i < n; i++)
            if(helper(i,1<<i,(1<<n) - 1))
                return true;

        return false;
    }
};