-
Notifications
You must be signed in to change notification settings - Fork 0
/
Count Lucky Permutations
35 lines (33 loc) · 1.17 KB
/
Count Lucky Permutations
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
// Time Complexity :- O(n*n*2^n);
// Space Complexity :- O(n*n*2^n);
long luckyPermutations(int N, int M, int arr[], int[][] graph) {
// Code here
HashSet<Integer>[] grap = new HashSet[N+1];
for(int i=0;i<=N;i++) grap[i] = new HashSet<>();
for(int[] g : graph) {
grap[g[0]].add(g[1]);
grap[g[1]].add(g[0]);
}
return f(grap,arr,0,-1,0,new Long[N][N+2][1<<N]);
}
long f(HashSet<Integer>[] graph,int[] a,int idx,int p_val,int visit,Long[][][] dp) {
if(idx>=a.length) return 1;
if(dp[idx][p_val+1][visit]!=null) return dp[idx][p_val+1][visit];
long ans=0;
for(int i=0;i<a.length;i++) {
if((visit&(1<<i))==0) {
// visit[i]=1;
if(p_val==-1) {
ans+=f(graph,a,idx+1,a[i],visit+(1<<i),dp);
} else {
if(graph[p_val].contains(a[i])) {
ans+=f(graph,a,idx+1,a[i],visit+(1<<i),dp);
}
}
// visit[i]=0;
}
}
return dp[idx][p_val+1][visit]=ans;
}
}