题目 #
给你一个下标从 0 开始的整数数组 nums ，它包含 n 个 互不相同 的正整数。如果 nums 的一个排列满足以下条件，我们称它是一个特别的排列：
- 对于
0 <= i < n - 1的下标i，要么nums[i] % nums[i+1] == 0，要么nums[i+1] % nums[i] == 0。
请你返回特别排列的总数目，由于答案可能很大，请将它对 ****109 + 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 <= 141 <= nums[i] <= 109
题解 #
我们用一个二进制的 mask 来表示尚未被选用的元素，若其下标对应的比特位为 1,则说明该元素尚未被选用。若 mask 为 0, 则表示所有元素均已使用。
之后我们使用深度搜索, dfs(mask, lastIdx), 每次，我们找出尚未被使用且符合条件的元素，更新 mask 和 lastIdx 递归调用 dfs, 若 mask 为 0, 则我们已经通过使用所有元素得到了一个排列。
代码 #
class Solution:
def specialPerm(self, nums: List[int]) -> int:
@cache
def dfs(unused, lastIdx):
if unused == 0:
return 1
count = 0
for idx, val in enumerate(nums):
if (unused >> idx) & 1 and (val % nums[lastIdx] == 0 or nums[lastIdx] % val == 0):
count += dfs(unused ^ (1 << idx), idx)
return count
n = len(nums)
MOD = 10 ** 9 + 7
unused = (1 << n) - 1
return sum([ dfs(unused ^ (1 << i), i) for i in range(n) ]) % MOD 复杂度 #
- 时间复杂度: O(n!)
- 空间复杂度: O(n!)