#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 ?
