描述
给你一个下标从 0 开始的整数数组 nums ，它包含 n 个 互不相同 的正整数。如果 nums 的一个排列满足以下条件，我们称它是一个特别的排列：
对于 0 <= i < n - 1 的下标 i ，要么 nums[i] % nums[i+1] == 0 ，要么 nums[i+1] % nums[i] == 0 。
请你返回特别排列的总数目，由于答案可能很大，请将它对 10^9 + 7 取余 后返回。
示例 1：
输入：nums = [2,3,6]
输出：2
解释：[3,6,2] 和 [2,6,3] 是 nums 两个特别的排列。
示例 2：
输入：nums = [1,4,3]
输出：2
解释：[3,1,4] 和 [4,1,3] 是 nums 两个特别的排列。
提示：
2 <= nums.length <= 14
1 <= nums[i] <= 10^9
思路
可以用图中的边表示两个数（结点）能满足题目描述的排列关系。因此问题转化为求出无向图中不重复经过所有节点的路径。
这个问题其实就是哈密顿通路问题。
一开始本人建图后，用dfs搜，超时了。然后改成了记忆化搜索。
进一步可改进地，可以用一个mask来表示搜索的状态（表示visited_map）（题目的2 <= nums.length <= 14其实就有暗示，结点数量有限）
代码
本人写的记忆化搜索
class Solution:def specialPerm(self, nums: List[int]) -> int:n = len(nums)self.adj_map = {}for i,num1 in enumerate(nums):for j in range(i+1,n):num2 = nums[j]if(num1 % num2 != 0 and num2 % num1 != 0): continueif(num1 not in self.adj_map): self.adj_map[num1] = set()if(num2 not in self.adj_map): self.adj_map[num2] = set()self.adj_map[num1].add(num2)self.adj_map[num2].add(num1)if(len(self.adj_map) != n): return 0head_nodes = []self.remain_nodes_set = set(nums)ret = 0self.memory_map = {}for node in nums:ret += self.dfs(node)return ret % 1000000007def dfs(self,head_node):status = (head_node,tuple(sorted(list(self.remain_nodes_set))))if(status in self.memory_map):return self.memory_map[status]if(len(self.remain_nodes_set) == 1):self.memory_map[status] = 1return 1ret = 0self.remain_nodes_set.remove(head_node)for n in self.adj_map[head_node]:if(n not in self.remain_nodes_set): continueret += self.dfs(n)self.remain_nodes_set.add(head_node)self.memory_map[status] = retreturn ret
这里给出评论区一位大佬写的，也是图的思路
class Solution:def specialPerm(self, nums: List[int]) -> int:n = len(nums)es = [[] for _ in range(n)]for i in range(n):for j in range(i+1,n):if nums[i]%nums[j]==0 or nums[j]%nums[i]==0:es[i].append(j)es[j].append(i)@cachedef dfs(state, last):return sum([dfs(1<<last^state,pre) for pre in es[last] if 1<<pre&state]) if 1<<last^state else 1return sum(dfs((1<<n)-1,i) for i in range(n))%int(1e9+7)