Special permutations

Array Dynamic Programming Bit Manipulation Bitmask

29.3% acceptance

Feb 25, 2026

588

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn special_perm(nums: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = nums.len();
    // dp[mask][last] = number of ways to arrange "mask" subset ending with nums[last]
    let mut dp = vec![vec![0i64; n]; 1 << n];
    for i in 0..n { dp[1 << i][i] = 1; }
    for mask in 1usize..(1 << n) {
      for last in 0..n {
        if dp[mask][last] == 0 { continue; }
        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]) % MOD;
          }
        }
      }
    }
    let full = (1 << n) - 1;
    (dp[full].iter().sum::<i64>() % MOD) as i32
  }
}