Special Permutations - Solution & Explanation

Problem Overview: You are given an array of distinct integers. The task is to count how many permutations exist such that for every adjacent pair (a, b), either a % b == 0 or b % a == 0. The result can be large, so it must be returned modulo 1e9 + 7.

Approach 1: Backtracking with Pruning (Time: O(n! * n), Space: O(n))

This approach generates permutations using classic backtracking. At each step, iterate through all unused elements and check if the current number forms a valid pair with the previously chosen number. If the divisibility condition fails, skip that branch immediately. This pruning significantly reduces the search space compared to generating all permutations. You maintain a visited structure to track which indices are already used and recursively build the permutation until its length reaches n.

The key insight is early rejection. Instead of building full permutations and validating afterward, the divisibility rule is checked while constructing the sequence. This approach is intuitive and useful for understanding the structure of the problem, but factorial growth still makes it expensive when n approaches the upper constraint.

Approach 2: Dynamic Programming with State Compression (Time: O(n^2 * 2^n), Space: O(n * 2^n))

The optimal solution uses dynamic programming combined with bitmask state compression. Represent the set of used indices with a bitmask of size n. Let dp[mask][last] store the number of valid permutations that use elements represented by mask and end at index last.

Transition by trying to append a new number. For every unused index next, check the divisibility condition with nums[last]. If valid, update dp[mask | (1 << next)][next]. The DP builds solutions incrementally from smaller subsets to larger ones. Because each state represents a unique combination of used elements, repeated computations from the backtracking approach disappear.

This method leverages the small constraint on n (typically ≤ 14). The total number of states is n * 2^n, and each transition checks up to n candidates. Precomputing which pairs satisfy the divisibility rule further speeds up transitions. The problem effectively becomes counting valid paths in a graph where edges exist between divisible numbers.

Recommended for interviews: Start by describing the backtracking idea to show you understand permutation generation and pruning. Then move to the optimized DP with bitmask solution. Interviewers typically expect the dynamic programming + bitmask approach because it reduces factorial complexity to O(n^2 * 2^n) while demonstrating mastery of subset DP on an array.