~~~~~↵
#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/)↵
↵
↵
↵
#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/)↵
↵
↵
↵
