Special Permutations - Solution & Explanation
Problem Statement
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, eithernums[i] % nums[i+1] == 0ornums[i+1] % nums[i] == 0.
Return the total number of special permutations. As the answer could be large, return it modulo 109 + 7.
Example 1:
Input: nums = [2,3,6] Output: 2 Explanation: [3,6,2] and [2,6,3] are the two special permutations of nums.
Example 2:
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 <= 141 <= nums[i] <= 109
Approach Overview
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.
Approach 1: Backtracking with Pruning
This approach utilizes backtracking to explore all permutations. As we generate permutations, we backtrack whenever a permutation no longer satisfies the special condition. To improve efficiency, pruning is done whenever an invalid sequence is detected.
This C code performs a backtracking search of all permutations of the input array nums. The function backtrack recursively builds permutations, skipping configurations that don't satisfy the special condition.
Complexity
Time Complexity: O(n!) where n is the number of elements in nums, as we generate permutations.
Space Complexity: O(n) due to the recursion stack and visited array.
Approach 2: Dynamic Programming with State Compression
This approach leverages dynamic programming to efficiently count special permutations by remembering the states of partial permutations using bitmasks. The DP table is used to store solutions to subproblems, avoiding repeated calculations.
This C solution uses a bitmask to track visited elements and stores intermediate results in a DP table. It recursively tries to form permutations by combining results of subproblems.
Complexity
Time Complexity: O(n^2 * 2^n) due to state exploration.
Space Complexity: O(n * 2^n) for DP table.
Approach 3: State Compression Dynamic Programming
We notice that the maximum length of the array in the problem does not exceed 14. Therefore, we can use an integer to represent the current state, where the i-th bit is 1 if the i-th number in the array has been selected, and 0 if it has not been selected.
We define f[i][j] as the number of schemes where the current selected integer state is i, and the index of the last selected integer is j. Initially, f[0][0]=0, and the answer is sum_{j=0}^{n-1}f[2^n-1][j].
Considering f[i][j], if only one number is currently selected, then f[i][j]=1. Otherwise, we can enumerate the index k of the last selected number. If the numbers corresponding to k and j meet the requirements of the problem, then f[i][j] can be transferred from f[i \oplus 2^j][k]. That is:
$
f[i][j]=
\begin{cases}
1, & i=2^j\
sum_{k=0}^{n-1}f[i \oplus 2^j][k], & i neq 2^j and nums[j] and nums[k] meet the requirements of the problem\
\end{cases}
The final answer is sum_{j=0}^{n-1}f[2^n-1][j]. Note that the answer may be very large, so we need to take the modulus of 10^9+7.
The time complexity is O(n^2 times 2^n), and the space complexity is O(n times 2^n). Here, n$ is the length of the array.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Backtracking with Pruning | Time Complexity: O(n!) where n is the number of elements in |
| Dynamic Programming with State Compression | Time Complexity: O(n^2 * 2^n) due to state exploration. |
| State Compression Dynamic Programming | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Pruning | O(n! * n) | O(n) | Good for understanding permutation generation and constraint pruning. Works for small n but becomes slow near upper limits. |
| DP with State Compression (Bitmask) | O(n^2 * 2^n) | O(n * 2^n) | Best general solution for n ≤ 14. Avoids recomputation by caching subset states. |
Video Solution
Leetcode Weekly contest 350 - Medium - Special Permutations • Prakhar Agrawal • 4,017 views views
Watch 6 more video solutions →Frequently Asked Questions
Is Special Permutations easy or hard?
How to solve Special Permutations in O(n^2 * 2^n)?
What is the best approach for Special Permutations?
Is Special Permutations asked at Google/Amazon/Meta?
What data structure is used in Special Permutations?
What is the time complexity of Special Permutations?
Special Permutations Python or Java solution approach?
Ready to solve this problem?
Practice Special Permutations with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor