Medium

Special Permutations

LAB

Return the number of permutations where every adjacent pair has one value divisible by the other, modulo 1000000007.

EXAMPLES

Example 1

Input
{
  "nums": [
    2,
    3,
    6
  ]
}

Output
2

FUNCTION SHAPE

nums: intArray→int

SOLUTION NOTE

Track which elements used (bitmask) and previous element. Try adding each unused element that satisfies the divisibility condition.

Reveal reference solution +

pythonREFERENCE

def specialPerm(self, nums: List[int]) -> int:
    n = len(nums)
    MOD = 10**9 + 7
    ALL = (1 << n) - 1

    @cache
    def dp(mask, prev):
        if mask == ALL: return 1
        res = 0
        for i in range(n):
            if mask & (1 << i): continue
            if nums[i] % prev == 0 or prev % nums[i] == 0:
                res = (res + dp(mask | (1 << i), nums[i])) % MOD
        return res

    return dp(0, 1)  # prev=1 so any nums[i] % 1 == 0

TimeO(n² × 2^n)

SpaceO(n × 2^n)

Open on LeetCode ↗