2741. Special Permutations

Problem Link

Description

---

You are given a 0-indexed integer array nums containing n distinct positive integers. A permutation of nums is called special if:

• For all indexes 0 <= i < n - 1, either nums[i] % nums[i+1] == 0 or nums[i+1] % nums[i] == 0.

Return the total number of special permutations. As the answer could be large, return it modulo 109 + 7.

 

Example 1:

Input: nums = [2,3,6]
Output: 2
Explanation: [3,6,2] and [2,6,3] are the two special permutations of nums.

Example 2:

Input: nums = [1,4,3]
Output: 2
Explanation: [3,1,4] and [4,1,3] are the two special permutations of nums.

 

Constraints:

• 2 <= nums.length <= 14
• 1 <= nums[i] <= 109

Solution

---

Python3

class Solution:
    def specialPerm(self, nums: List[int]) -> int:
        N = len(nums)
        M = 10 ** 9 + 7
        graph = defaultdict(list)
        full_mask = (1 << N) - 1
        
        
        for i in range(N):
            for j in range(N):
                if i == j: continue
                
                if nums[i] % nums[j] == 0 or nums[j] % nums[i] == 0:
                    graph[i].append(j)
        
        @cache
        def go(index, mask):
            if mask == full_mask: return 1
            
            ans = 0
            
            for adj in graph[index]:
                if (mask & (1 << adj)) == 0 and (nums[index] % nums[adj] == 0 or nums[adj] % nums[index] == 0):
                    ans = (ans + go(adj, mask ^ (1 << adj))) % M
            
            return ans
                    
        
        res = 0
        
        for i in range(N):
            res = (res + go(i, 1 << i)) % M
        
        return res