Problem

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 **10^9 + 7.

Examples

Example 1

1
2
3

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

Example 2

1
2
3

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] <= 10^9

Solution

Method 1 – Bitmask Dynamic Programming

Intuition

To count all special permutations, we use dynamic programming with bitmasking. At each step, we keep track of which numbers have been used and the last number added to the permutation. For each unused number, we check if it can be placed next to the last number according to the divisibility condition. This approach efficiently explores all valid permutations without generating them explicitly.

Approach

  1. Use a DP table where dp[mask][last] is the number of ways to build a permutation using the subset ‘mask’ ending with index ’last’.
  2. Initialize dp[1 « i][i] = 1 for all i (starting permutations with each number).
  3. For each mask and last, try to add every unused number ’next’. If nums[last] % nums[next] == 0 or nums[next] % nums[last] == 0, update dp[mask | (1 « next)][next].
  4. Sum all dp[full_mask][i] for all i to get the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int specialPerm(vector<int>& nums) {
        int n = nums.size(), mod = 1e9+7;
        vector<vector<int>> dp(1<<n, vector<int>(n));
        for (int i = 0; i < n; ++i) dp[1<<i][i] = 1;
        for (int mask = 0; mask < (1<<n); ++mask) {
            for (int last = 0; last < n; ++last) {
                if (!(mask & (1<<last))) continue;
                for (int next = 0; next < n; ++next) {
                    if (mask & (1<<next)) continue;
                    if (nums[last] % nums[next] == 0 || nums[next] % nums[last] == 0) {
                        dp[mask | (1<<next)][next] = (dp[mask | (1<<next)][next] + dp[mask][last]) % mod;
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) ans = (ans + dp[(1<<n)-1][i]) % mod;
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

func specialPerm(nums []int) int {
    n, mod := len(nums), int(1e9+7)
    dp := make([][]int, 1<<n)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    for i := 0; i < n; i++ {
        dp[1<<i][i] = 1
    }
    for mask := 0; mask < 1<<n; mask++ {
        for last := 0; last < n; last++ {
            if mask&(1<<last) == 0 {
                continue
            }
            for next := 0; next < n; next++ {
                if mask&(1<<next) != 0 {
                    continue
                }
                if nums[last]%nums[next] == 0 || nums[next]%nums[last] == 0 {
                    dp[mask|(1<<next)][next] = (dp[mask|(1<<next)][next] + dp[mask][last]) % mod
                }
            }
        }
    }
    ans := 0
    for i := 0; i < n; i++ {
        ans = (ans + dp[(1<<n)-1][i]) % mod
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int specialPerm(int[] nums) {
        int n = nums.length, mod = (int)1e9+7;
        int[][] dp = new int[1<<n][n];
        for (int i = 0; i < n; ++i) dp[1<<i][i] = 1;
        for (int mask = 0; mask < (1<<n); ++mask) {
            for (int last = 0; last < n; ++last) {
                if ((mask & (1<<last)) == 0) continue;
                for (int next = 0; next < n; ++next) {
                    if ((mask & (1<<next)) != 0) continue;
                    if (nums[last] % nums[next] == 0 || nums[next] % nums[last] == 0) {
                        dp[mask | (1<<next)][next] = (dp[mask | (1<<next)][next] + dp[mask][last]) % mod;
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) ans = (ans + dp[(1<<n)-1][i]) % mod;
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    fun specialPerm(nums: IntArray): Int {
        val n = nums.size
        val mod = 1_000_000_007
        val dp = Array(1 shl n) { IntArray(n) }
        for (i in 0 until n) dp[1 shl i][i] = 1
        for (mask in 0 until (1 shl n)) {
            for (last in 0 until n) {
                if (mask and (1 shl last) == 0) continue
                for (next in 0 until n) {
                    if (mask and (1 shl next) != 0) continue
                    if (nums[last] % nums[next] == 0 || nums[next] % nums[last] == 0) {
                        dp[mask or (1 shl next)][next] = (dp[mask or (1 shl next)][next] + dp[mask][last]) % mod
                    }
                }
            }
        }
        var ans = 0
        for (i in 0 until n) ans = (ans + dp[(1 shl n) - 1][i]) % mod
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def specialPerm(self, nums: list[int]) -> int:
        n, mod = len(nums), 10**9+7
        dp = [[0]*n for _ in range(1<<n)]
        for i in range(n):
            dp[1<<i][i] = 1
        for mask in range(1<<n):
            for last in range(n):
                if not (mask & (1<<last)):
                    continue
                for nxt in range(n):
                    if mask & (1<<nxt): continue
                    if nums[last] % nums[nxt] == 0 or nums[nxt] % nums[last] == 0:
                        dp[mask|(1<<nxt)][nxt] = (dp[mask|(1<<nxt)][nxt] + dp[mask][last]) % mod
        return sum(dp[(1<<n)-1][i] for i in range(n)) % mod
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn special_perm(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let modv = 1_000_000_007;
        let mut dp = vec![vec![0; n]; 1<<n];
        for i in 0..n { dp[1<<i][i] = 1; }
        for mask in 0..(1<<n) {
            for last in 0..n {
                if mask & (1<<last) == 0 { continue; }
                for next in 0..n {
                    if mask & (1<<next) != 0 { continue; }
                    if nums[last] % nums[next] == 0 || nums[next] % nums[last] == 0 {
                        dp[mask | (1<<next)][next] = (dp[mask | (1<<next)][next] + dp[mask][last]) % modv;
                    }
                }
            }
        }
        let mut ans = 0;
        for i in 0..n { ans = (ans + dp[(1<<n)-1][i]) % modv; }
        ans
    }
}

Complexity

  • ⏰ Time complexity: O(n^2 * 2^n) – Each mask and last index is processed, and for each, we try all possible next indices.
  • 🧺 Space complexity: O(n * 2^n) – For the DP table.