2741. 特别的排列

题目

给你一个下标从 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 <= 14

1 <= 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!)