You are given an array arr[ ] of integers having N elements and a non-weighted undirected graph having N nodes and M edges. The details of each edge in the graph is given to you in the form of list of list. 
Your task is to find the number of lucky permutations of the given array. 
An array permutation is said to be lucky if for every node V_{i  }[1 <= i <= N-1] in the array there exists an edge between the nodes V_{i }and V_{i+1 }in the given graph.
Example 1:
Input:
N = 3, M = 2
arr = {1, 2, 3}
graph = {{3, 1}, {1, 2}}
Output:
2
Explanation:
All possible permutations of the 
array are as follows-
{1,2,3}: There is an edge between 1 and 
2 in the graph but not betwen 2 and 3.
{2,1,3}: There is an edge between (2,1)
and (1,3) in the graph.
{3,1,2}: There is an edge between (3,1)
and (1,2) in the graph.
Out of the 3 possible permutations, 
2 are lucky. Therefore, answer is 2.
Example 2:
Input:
N = 2, M = 1
arr = {1, 1}
graph = {{1, 2}}
Output :
0
Explanation:
There is no lucky permutation in the 
given graph. 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function luckyPermutations() which takes the two integers N and M, an array arr[ ] and a list of lists named graph of size M as input parameters and returns the count of lucky permutations.
Expected Time Complexity: O(N^{2}*2^{N})
Expected Auxiliary Space: O(N*2^{N})
Constraints:
2 ≤ N ≤ 15
1 ≤ M ≤ (N*(N-1))/2
1 ≤  arr[i], graph[i][j] ≤ N 
There are no self-loops and repeated edges in the graph.

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Graph algorithms

Data structures

Starter code: #User function Template for python3



class Solution: 

    def luckyPermutations(self, N, M, arr, graph):

        # Code here

Solutions:
from collections import defaultdict

class Solution:

	def luckyPermutations(self, N, M, arr, graph):
		ind = defaultdict(list)
		for (i, a) in enumerate(arr):
			ind[a].append(i)
		dp = [[0 for j in range(1 << N)] for i in range(N)]
		for i in range(N):
			dp[i][1 << i] = 1
		for mask in range(-1, 1 << N):
			for (u, v) in graph:
				for i in ind[u]:
					for j in ind[v]:
						if mask & 1 << i and mask & 1 << j:
							(maski, maskj) = (mask ^ 1 << i, mask ^ 1 << j)
							dp[i][mask] += dp[j][maski]
							dp[j][mask] += dp[i][maskj]
		return sum((dp[i][(1 << N) - 1] for i in range(N)))


class Solution:

	def luckyPermutations(self, N, M, arr, graph):
		dp = [[0 for j in range(1 << N)] for j in range(N)]
		for i in range(N):
			dp[i][1 << i] = 1
		adj = [[0 for j in range(N)] for j in range(N)]
		for edge in graph:
			adj[edge[0] - 1][edge[1] - 1] = 1
			adj[edge[1] - 1][edge[0] - 1] = 1
		for bitmask in range(1, 1 << N):
			for i in range(N):
				if 1 & bitmask >> i:
					for j in range(N):
						if j != i and arr[j] != arr[i] and 1 & bitmask >> j and adj[arr[i] - 1][arr[j] - 1]:
							dp[i][bitmask] += dp[j][bitmask ^ 1 << i]
		ans = 0
		for i in range(N):
			ans += dp[i][(1 << N) - 1]
		return ans


from collections import defaultdict, Counter
from math import factorial

class Solution:

	def luckyPermutations(self, N, M, A, graph):

		def _lobit(n):
			return n & -n
		A = [v - 1 for v in A]
		adjs = defaultdict(list)
		(prev, cur) = ({}, {})
		vimap = [0] * N
		for (i, v) in enumerate(A):
			vimap[v] |= 1 << i
		for (a, b) in graph:
			if a == b:
				continue
			(a, b) = (a - 1, b - 1)
			adjs[a].append(b)
			adjs[b].append(a)
		for v in range(N):
			if not vimap[v]:
				continue
			sig = _lobit(vimap[v])
			prev[sig, v] = 1
		for _ in range(2, N + 1):
			for ((sig, ev), cnt) in prev.items():
				for cand in adjs[ev]:
					bits = vimap[cand]
					availbits = bits & ~sig
					if availbits:
						newsig = sig | _lobit(availbits)
						cur[newsig, cand] = cnt + cur.get((newsig, cand), 0)
			(prev, cur) = (cur, prev)
			cur.clear()
		fac_mul = 1
		for v in Counter(A).values():
			fac_mul *= factorial(v)
		ans = sum(prev.values()) * fac_mul
		return ans


import sys
sys.setrecursionlimit(100000000)

class Solution:
	conn = list()
	dp = list()

	def rec(self, arr, mask, prev):
		if prev != -1 and self.dp[mask][prev] != -1:
			return self.dp[mask][prev]
		if mask == 0:
			return 1
		count = 0
		for i in range(len(arr)):
			if mask & 1 << i > 0:
				curr = arr[i]
				if prev == -1 or self.conn[prev][curr]:
					count += self.rec(arr, mask ^ 1 << i, curr)
		self.dp[mask][prev] = count
		return count

	def luckyPermutations(self, N, M, arr, graph):
		self.conn = [[False] * (N + 1) for _ in range(N + 2)]
		self.dp = [[-1] * 16 for _ in range((1 << 16) + 1)]
		mask = (1 << N) - 1
		for one_graph in graph:
			self.conn[one_graph[0]][one_graph[1]] = True
			self.conn[one_graph[1]][one_graph[0]] = True
		return self.rec(arr, mask, -1)


class Solution:

	def luckyPermutations(self, N, M, arr, graph):
		edges = set()
		for [a, b] in graph:
			edges.add((a, b))
			edges.add((b, a))
		dp = dict()
		ans = 0
		for i in range(N):
			state = (i << 16) + (1 << i)
			ans += self.backtracking(state, dp, arr, edges)
		return ans

	def backtracking(self, state, dp, arr, edges):
		if state not in dp:
			i = state >> 16
			visited = state - (i << 16)
			if visited + 1 == 1 << len(arr):
				ans = 1
			else:
				ans = 0
				for j in range(len(arr)):
					if i == j or (arr[i], arr[j]) not in edges or visited & 1 << j != 0:
						continue
					state2 = visited + (j << 16) + (1 << j)
					ans += self.backtracking(state2, dp, arr, edges)
			dp[state] = ans
		return dp[state]


class Solution:

	def genKey(self, v1, v2):
		return str(v1) + ',' + str(v2)

	def helper(self, mask, arr, prev, adj, dp):
		key = self.genKey(mask, prev)
		if key in dp:
			return dp[key]
		if mask == 0:
			return 1
		cnt = 0
		for i in range(len(arr)):
			bitset = 1 << i
			if mask & bitset:
				curr = arr[i]
				if prev == -1 or adj[curr][prev]:
					cnt += self.helper(mask ^ bitset, arr, curr, adj, dp)
		dp[key] = cnt
		return cnt

	def luckyPermutations(self, N, M, arr, graph):
		adj = [[False for _ in range(16)] for _ in range(16)]
		for i in range(M):
			adj[graph[i][0]][graph[i][1]] = True
			adj[graph[i][1]][graph[i][0]] = True
		mask = (1 << N) - 1
		dp = {}
		return self.helper(mask, arr, -1, adj, dp)


class Solution:

	def luckyPermutations(self, N, M, arr, graph):
		adj_matrix = [[False] * N for i in range(N)]
		for i in range(M):
			u = graph[i][0] - 1
			v = graph[i][1] - 1
			adj_matrix[u][v] = True
			adj_matrix[v][u] = True
		total = pow(2, N)
		dp = [[0] * total for i in range(N)]
		for i in range(N):
			dp[i][1 << N - 1 - i] = 1
		for mask in range(total):
			for i in range(N):
				i_selected = 1 << N - 1 - i
				if mask & i_selected:
					rem_mask = mask ^ i_selected
					if rem_mask > 0:
						for j in range(N):
							j_selected = 1 << N - 1 - j
							if rem_mask & j_selected and adj_matrix[arr[i] - 1][arr[j] - 1]:
								dp[i][mask] += dp[j][rem_mask]
		ans = 0
		for i in range(N):
			ans += dp[i][total - 1]
		return ans


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def luckyPermutations(self, N, M, arr, graph):
		adjmatrix = [[0 for i in range(N)] for j in range(N)]
		for x in graph:
			node1 = x[0] - 1
			node2 = x[1] - 1
			adjmatrix[node1][node2] = 1
			adjmatrix[node2][node1] = 1
		dp = [[-1 for i in range(1 << N)] for j in range(16)]
		mask = (1 << N) - 1
		return self.helper(mask, arr, dp, -1, adjmatrix)

	def helper(self, mask, arr, dp, prev, adjmatrix):
		if mask == 0:
			return 1
		if prev != -1 and dp[prev][mask] != -1:
			return dp[prev][mask]
		count = 0
		for i in range(len(arr)):
			if mask & 1 << i and (prev == -1 or self.checkedge(arr[i], prev, adjmatrix)):
				mask ^= 1 << i
				count += self.helper(mask, arr, dp, arr[i], adjmatrix)
				mask ^= 1 << i
		dp[prev][mask] = count
		return count

	def checkedge(self, val1, val2, adjmatrix):
		if adjmatrix[val1 - 1][val2 - 1] and adjmatrix[val2 - 1][val1 - 1]:
			return True
		return False


class Solution:

	def dfs(self, arr, mask, states, N, adj):
		used = []
		unused = []
		for i in range(N):
			if mask & 1 << i:
				used.append(i)
			else:
				unused.append(i)
		for x in used:
			states[x][mask] = 0
			for y in unused:
				if adj[arr[x] - 1][arr[y] - 1]:
					new_mask = mask + (1 << y)
					if states[y][new_mask] == -1:
						self.dfs(arr, new_mask, states, N, adj)
					states[x][mask] += states[y][new_mask]

	def luckyPermutations(self, N, M, arr, graph):
		adj = [[0 for i in range(N)] for j in range(N)]
		for (x, y) in graph:
			adj[x - 1][y - 1] = 1
			adj[y - 1][x - 1] = 1
		num_masks = 1 << N
		states = [[-1 for i in range(num_masks)] for j in range(N)]
		ans = 0
		for i in range(N):
			states[i][(1 << N) - 1] = 1
		for i in range(N):
			self.dfs(arr, 1 << i, states, N, adj)
			ans += states[i][1 << i]
		return ans


class Solution:

	def luckyPermutations(self, n, m, arr, graph):
		adj = [[0 for i in range(n + 1)] for i in range(n + 1)]
		dp = [[-1 for i in range(1 << n)] for i in range(n + 1)]
		for i in range(len(graph)):
			adj[graph[i][0]][graph[i][1]] = 1
			adj[graph[i][1]][graph[i][0]] = 1

		def solve(mask, prev):
			if mask == 0:
				return 1
			if prev != -1 and dp[prev][mask] != -1:
				return dp[prev][mask]
			res = 0
			for i in range(n):
				if mask & 1 << i > 0:
					if prev == -1 or adj[prev][arr[i]]:
						res += solve(mask ^ 1 << i, arr[i])
			dp[prev][mask] = res
			return res
		return solve((1 << n) - 1, -1)


from typing import List

class Solution:

	def luckyPermutations(self, N: int, M: int, arr: List[int], graph: List[List[int]]) -> int:
		adj = [[False] * N for _ in range(N)]
		for edge in graph:
			adj[edge[0] - 1][edge[1] - 1] = adj[edge[1] - 1][edge[0] - 1] = True
		dp = [[0] * (1 << N) for _ in range(N)]
		for i in range(N):
			dp[i][1 << i] = 1
		for subset in range(1 << N):
			for curr in range(N):
				if not subset & 1 << curr:
					continue
				for prev in range(N):
					if curr == prev or arr[curr] == arr[prev]:
						continue
					if not subset & 1 << prev:
						continue
					if not adj[arr[prev] - 1][arr[curr] - 1]:
						continue
					dp[curr][subset] += dp[prev][subset ^ 1 << curr]
		ans = 0
		for i in range(N):
			ans += dp[i][(1 << N) - 1]
		return ans


import sys
sys.setrecursionlimit(1000000)

def f(adj, A, mask, prev, dp):
	if mask == 0:
		return 1
	if dp[prev][mask] != -1:
		return dp[prev][mask]
	c = 0
	for i in range(len(A)):
		if mask & 1 << i > 0:
			if prev == -1 or adj[A[prev]][A[i]]:
				c += f(adj, A, mask ^ 1 << i, i, dp)
	dp[prev][mask] = c
	return c

class Solution:

	def luckyPermutations(self, N, M, A, graph):
		adj = [[0 for j in range(N + 1)] for j in range(N + 1)]
		sz = 1 << N
		for (u, v) in graph:
			adj[u][v] = 1
			adj[v][u] = 1
		dp = [[-1 for i in range(sz)] for i in range(N + 1)]
		ans = f(adj, A, sz - 1, -1, dp)
		return ans


class Solution:

	def luckyPermutations(self, N, M, arr, graph):
		ans = 0
		d = {}
		for item in arr:
			if item in d:
				d[item] += 1
			else:
				d[item] = 1
		grph = [[] for _ in range(N)]
		for (a, b) in graph:
			grph[a - 1].append(b - 1)
			grph[b - 1].append(a - 1)
		dp = [[-1 for _ in range(1 << N)] for __ in range(N)]
		visited = [0 for _ in range(N)]
		for i in d:
			ans += self.get(grph, i - 1, N - 1, visited, d, dp)
		return ans

	def get(self, graph, node, N, visited, d, dp):
		b = 0
		bit = 1
		for i in d:
			for j in range(visited[i - 1]):
				b |= bit
				bit <<= 1
			bit <<= d[i] - visited[i - 1]
		if node + 1 not in d:
			return 0
		elif N == 0:
			return 1
		elif dp[node][b] != -1:
			return dp[node][b]
		else:
			visited[node] += 1
			ans = 0
			for item in graph[node]:
				if visited[item] < d.get(item + 1, 0):
					ans += self.get(graph, item, N - 1, visited, d, dp) * (d[node + 1] - visited[node] + 1)
			visited[node] -= 1
			dp[node][b] = ans
			return ans


import collections

class Solution:

	def luckyPermutations(self, N, M, arr, graph):
		dp = [[0] * (1 << N) for i in range(N)]
		edges = collections.defaultdict(set)
		for (a, b) in graph:
			edges[a - 1].add(b - 1)
			edges[b - 1].add(a - 1)
		for i in range(N):
			dp[i][1 << i] = 1
		for subset in range(1 << N):
			for curr in range(N):
				if subset & 1 << curr == 0:
					continue
				for prev in range(N):
					if curr == prev or arr[curr] == arr[prev]:
						continue
					if subset & 1 << prev == 0:
						continue
					if arr[curr] - 1 not in edges[arr[prev] - 1]:
						continue
					dp[curr][subset] += dp[prev][subset ^ 1 << curr]
		ans = 0
		for i in range(N):
			ans += dp[i][(1 << N) - 1]
		return ans


from collections import defaultdict

class Solution:

	def luckyPermutations(self, N, M, arr, graph):
		ind = defaultdict(list)
		for (i, a) in enumerate(arr):
			ind[a].append(i)
		dp = [[0 for j in range(1 << N)] for i in range(N)]
		for i in range(N):
			dp[i][1 << i] = 1
		for bitmask in range(1, 1 << N):
			for (u, v) in graph:
				for i in ind[u]:
					for j in ind[v]:
						if bitmask & 1 << i and bitmask & 1 << j:
							(bitmaski, bitmaskj) = (bitmask ^ 1 << i, bitmask ^ 1 << j)
							dp[i][bitmask] += dp[j][bitmaski]
							dp[j][bitmask] += dp[i][bitmaskj]
		return sum((dp[i][(1 << N) - 1] for i in range(N)))


class Solution:

	def luckyPermutations(self, N, M, arr, graph):
		mat = [[0 for i in range(N + 1)] for i in range(N + 1)]
		for (i, j) in graph:
			mat[i][j] = 1
			mat[j][i] = 1
		dp = [[0 for i in range(1 << N)] for i in range(N)]
		for i in range(N):
			dp[i][1 << i] = 1
		for bit in range(1, 1 << N):
			for i in range(N):
				if 1 & bit >> i:
					for j in range(N):
						if i != j and arr[i] != arr[j] and 1 & bit >> j:
							if mat[arr[i]][arr[j]]:
								dp[i][bit] += dp[j][bit ^ 1 << i]
		ans = 0
		for i in dp:
			ans += i[-1]
		return ans


class Solution:

	def luckyPermutations(self, N, M, arr, graph):
		arr.sort()
		adjacency_list = self.construct_graph(graph, N)
		return self.generate_permutation(-1, arr, adjacency_list, 0, N, {})

	def construct_graph(self, graph, N):
		adjacency_list = [[False] * (N + 1) for __ in range(N + 1)]
		for arr in graph:
			adjacency_list[arr[0]][arr[1]] = True
			adjacency_list[arr[1]][arr[0]] = True
		return adjacency_list

	def generate_permutation(self, prev, arr, graph, state, N, dp):
		if N == 0:
			return 1
		res = 0
		cur_dp = dp.get(state, {})
		for (indx, num) in enumerate(arr):
			cur_indx = 1 << indx
			if cur_indx & state == 0 and (prev == -1 or graph[num][prev]):
				if cur_dp.get(num, -1) != -1:
					res += cur_dp[num]
					continue
				temp = self.generate_permutation(num, arr, graph, state | cur_indx, N - 1, dp)
				res += temp
				cur_dp[num] = temp
		dp[state] = cur_dp
		return res


class Solution:

	def dfs(self, cur, mask, g, dp, total, N, arr):
		if mask == total:
			return 1
		if dp[cur][mask] != -1:
			return dp[cur][mask]
		temp = 0
		for i in range(N):
			if mask & 1 << i > 0 or g[arr[cur] - 1][arr[i] - 1] != 1:
				continue
			temp += self.dfs(i, mask | 1 << i, g, dp, total, N, arr)
		dp[cur][mask] = temp
		return dp[cur][mask]

	def luckyPermutations(self, N, M, arr, graph):
		ans = 0
		total = 2 ** N - 1
		temp = set()
		for i in arr:
			temp.add(i)
		dp = [[-1 for i in range(2 ** N)] for j in range(N)]
		g = [[-1 for i in range(N)] for j in range(N)]
		for x in graph:
			g[x[0] - 1][x[1] - 1] = 1
			g[x[1] - 1][x[0] - 1] = 1
		ans = 0
		for i in range(N):
			ans += self.dfs(i, 1 << i, g, dp, total, N, arr)
		return ans