How to avoid duplicates in Count of Hamiltonian Paths ?
Difference between en1 and en2, changed 16 character(s)
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
int all;↵

int dfs(int u, int mask, vector<vector<int>>& gp, int n, int m, int dp[][1 << 11], vector<int>ps = {}){↵
    //ps.push_back(u);↵
if(mask == all){↵
        for(auto pp: ps){↵
            cout<<pp<<" ";↵
        }↵
        cout<<endl;↵
        return 1;↵
}↵
int res = 0;↵
// if(dp[u][mask] != -1)return dp[u][mask];↵
for(int v: gp[u]){↵
if((mask >> v) & 1)continue;↵
ps.push_back(v);↵
res += dfs(v, mask | (1 << v), gp, n, m, dp, ps);↵
ps.pop_back();↵
}↵
return dp[u][mask] = res;↵
}↵
int main(){↵
int t;↵
t = 1;↵
while(t--){↵
int n;↵
cin>>n;↵
int m;↵
cin>>m;↵
all = (1 << n) - 1;↵
int dp[11][1 << 11];↵
memset(dp, -1, sizeof(dp));↵
vector<vector<int>>gp(n + 1);↵
for(int i = 1; i <= m; i++){↵
int u, v;↵
cin>>u>>v;↵
u--, v--;↵
gp[u].push_back(v);↵
gp[v].push_back(u);↵
}↵

int res = 0;↵
for(int i = 0; i < n; i++){↵
//memset(dp, -1, sizeof(dp));↵
res += dfs(i, 1 << i, gp, n, m, dp, {i});↵
}↵
cout<<res<<endl;↵
}↵
}↵
~~~~~↵

For the Test case ↵

7 10↵
6 7↵
3 7↵
1 5↵
3 2↵
7 1↵
5 2↵
1 7↵
3 6↵
5 7↵
5 4↵

Output is 8 after debugging we can see some of them are counted 2 times.↵

`0 6 5 2 1 4 3`
`0 6 5 2 1 4 3`
`1 2 5 6 0 4 3`
`1 2 5 6 0 4 3`
`3 4 0 6 5 2 1`
`3 4 0 6 5 2 1`
`3 4 1 2 5 6 0`
`3 4 1 2 5 6 0`
8↵

Correct answer is 4. Please help in how can i fix this code ?↵

[Problem link](https://www.hackerearth.com/practice/algorithms/graphs/hamiltonian-path/practice-problems/algorithm/micro-and-permutations/)↵



History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English acash 2024-07-26 14:14:01 16
en1 English acash 2024-07-26 14:12:37 1609 Initial revision (published)