# Special Permutations
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/special-permutations)
Canonical: https://scaleengineer.com/dsa/problems/special-permutations
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array
---
## 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** `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 <= 14`
* `1 <= nums[i] <= 109`

# Approaches
## Brute-Force with Permutation Generation
This approach involves generating every possible arrangement (permutation) of the `nums` array. For each generated permutation, it performs a check to see if it satisfies the "special" condition. If it does, a counter is incremented. This method is the most straightforward to conceptualize but is computationally very expensive.
**Time:** O(n! * n) - There are `n!` possible permutations to generate. For each permutation, we take O(n) time to check if it's special. This makes the approach infeasible for `n > 10`. · **Space:** O(n) - The space is dominated by the recursion stack depth and the list used to store the current permutation, both of which can go up to size `n`.
**Pros:** Simple to understand and implement.; Correctly solves the problem for very small values of `n`.
**Cons:** Extremely inefficient due to its factorial time complexity.; Will result in a 'Time Limit Exceeded' error on platforms like LeetCode for constraints like n=14.
### Explanation
The core idea is to explore all `n!` permutations of the input array. We can use a recursive helper function to build these permutations. The function maintains a list for the current permutation being built and a boolean array to keep track of which numbers from the original array have been used.

Once a full permutation of length `n` is formed, we validate it. The validation involves iterating through the permutation from the first to the second-to-last element and checking the divisibility condition for each adjacent pair (`nums[i]` and `nums[i+1]`). If all pairs in the permutation satisfy the condition, we increment our total count of special permutations. Since the answer can be large, the count is maintained modulo `10^9 + 7`.

```java
class Solution {
    long count = 0;
    int MOD = 1_000_000_007;

    public int specialPerm(int[] nums) {
        List<Integer> p = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        generatePermutations(nums, p, used);
        return (int) count;
    }

    private void generatePermutations(int[] nums, List<Integer> p, boolean[] used) {
        if (p.size() == nums.length) {
            if (isSpecial(p)) {
                count = (count + 1) % MOD;
            }
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                used[i] = true;
                p.add(nums[i]);
                generatePermutations(nums, p, used);
                p.remove(p.size() - 1); // Backtrack
                used[i] = false;
            }
        }
    }

    private boolean isSpecial(List<Integer> p) {
        for (int i = 0; i < p.size() - 1; i++) {
            if (p.get(i) % p.get(i + 1) != 0 && p.get(i + 1) % p.get(i) != 0) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Create a recursive helper function, `generatePermutations(nums, current_permutation, used_flags)`, to generate all permutations of `nums`.
- The function works as follows:
  - **Base Case:** If the `current_permutation` has `n` elements, it's a complete permutation. Check if it's a special permutation using a helper function `isSpecial()`.
  - If it is special, increment the `count` (with modulo arithmetic).
  - **Recursive Step:** Iterate through each number in the original `nums` array. If a number hasn't been used, mark it as used, add it to `current_permutation`, and make a recursive call. After the call returns, backtrack by removing the number and unmarking it.
- The `isSpecial(permutation)` helper function iterates from `i = 0` to `n-2` and checks if `perm[i] % perm[i+1] == 0` or `perm[i+1] % perm[i] == 0` for all adjacent pairs. If any pair fails this condition, it returns `false`.
- Start the process by calling `generatePermutations` with an empty permutation.
- Return the final `count`.

## Backtracking with Pruning
This approach improves upon brute-force by integrating the validity check into the permutation generation process. Instead of generating a full permutation and then checking it, we build the permutation one element at a time. We only add a new element if it satisfies the "special" condition with the previous element. If at any point an element cannot be added, we prune this entire branch of the search tree, thus avoiding the generation of many invalid permutations.
**Time:** O(n!) - In the worst case, the complexity is still factorial. However, for average cases where the graph of divisibility is sparse, the performance is much better than O(n! * n) because many branches are pruned early. · **Space:** O(n) - For the recursion stack depth and the list storing the current permutation.
**Pros:** Significantly more efficient than the brute-force approach due to pruning.; Conceptually builds on the idea of permutation generation, making it relatively easy to understand.
**Cons:** The time complexity is still factorial in the worst-case scenario (when all numbers are mutually divisible, forming a complete graph).; It can be too slow for the given constraints as it doesn't store results of subproblems, leading to redundant computations.
### Explanation
We employ a recursive depth-first search (DFS) strategy. The recursive function explores paths that could form a special permutation. It keeps track of the permutation being built and the numbers that have already been used.

At each step of the recursion, we try to append an unused number to the current partial permutation. A number can be appended only if it's the first number in the permutation or if it satisfies the divisibility rule with the last number currently in the permutation. If it does, we add it and recurse. If not, we discard this choice and try the next unused number. This pruning of invalid paths makes the search more efficient than the naive brute-force method.

```java
class Solution {
    long count = 0;
    int MOD = 1_000_000_007;
    int n;

    public int specialPerm(int[] nums) {
        this.n = nums.length;
        boolean[] used = new boolean[n];
        dfs(new ArrayList<>(), used, nums);
        return (int) count;
    }

    private void dfs(List<Integer> currentPerm, boolean[] used, int[] nums) {
        if (currentPerm.size() == n) {
            count = (count + 1) % MOD;
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                if (currentPerm.isEmpty() || 
                    (currentPerm.get(currentPerm.size() - 1) % nums[i] == 0) || 
                    (nums[i] % currentPerm.get(currentPerm.size() - 1) == 0)) {
                    
                    used[i] = true;
                    currentPerm.add(nums[i]);
                    dfs(currentPerm, used, nums);
                    currentPerm.remove(currentPerm.size() - 1); // Backtrack
                    used[i] = false;
                }
            }
        }
    }
}
```
### Algorithm
- Use a recursive Depth-First Search (DFS) function, `dfs(current_permutation, used_flags)`, to build special permutations element by element.
- The function works as follows:
  - **Base Case:** If the `current_permutation` size is `n`, we have successfully built a full special permutation. Increment the total count (modulo `10^9 + 7`) and return.
  - **Recursive Step:** Iterate through all numbers `nums[i]`.
  - If `nums[i]` has not been used yet, check if it can be appended to the `current_permutation`.
  - The condition is: the permutation is empty, OR `nums[i]` is divisible by the last element, OR the last element is divisible by `nums[i]`.
  - If the condition is met, mark `nums[i]` as used, add it to the permutation, and make a recursive call: `dfs(new_permutation, new_used_flags)`.
  - After the recursive call returns, backtrack by removing `nums[i]` from the permutation and unmarking it as used. This allows exploring other possibilities.
- The initial call is made with an empty permutation.

## Dynamic Programming with Bitmasking
This is the most efficient approach for the given constraints. It uses dynamic programming with bitmasking to avoid the redundant computations inherent in the recursive backtracking solution. The state of our DP is defined by the subset of numbers used in the permutation and the last number of the permutation.
**Time:** O(n^2 * 2^n) - There are `n * 2^n` states `(mask, lastIdx)`. For each state, we iterate through `n` possible previous elements to compute the result. Thus, the total time is `n * 2^n * n`. · **Space:** O(n * 2^n) - We use a 2D array for memoization of size `(1 << n) x n`.
**Pros:** Highly efficient and guaranteed to pass within the time limits for n <= 14.; It's a standard and powerful technique for permutation-related problems on small sets (Traveling Salesperson Problem, etc.).
**Cons:** The space complexity of O(n * 2^n) can be large, though it's acceptable for n <= 14.; Can be less intuitive to grasp compared to straightforward backtracking.
### Explanation
We can think of this problem as finding the number of Hamiltonian paths in a graph. The vertices are the numbers from the `nums` array, and an edge connects two vertices `u` and `v` if `u % v == 0` or `v % u == 0`.

A Hamiltonian path visits each vertex exactly once. We need to count all such paths.

We define a DP state `dp[mask][i]`, which stores the number of special partial permutations that use the set of numbers represented by `mask` and end with the number `nums[i]`. The `mask` is an integer where the `j`-th bit is set to 1 if `nums[j]` has been used.

This can be implemented with a top-down recursive approach with memoization. The function `solve(mask, last_idx)` computes our DP state. The base case is a permutation of length 1. In the recursive step, we try to extend shorter valid permutations by one element. To find `dp[mask][i]`, we look at all valid permutations for the sub-mask `mask` excluding `i`, and for each of those permutations ending in `j`, we check if `i` can follow `j`. If it can, we add `dp[sub-mask][j]` to our result for `dp[mask][i]`.

The final answer is the sum of `dp[final_mask][i]` for all `i`, where `final_mask` has all `n` bits set, representing all numbers being used.

```java
import java.util.Arrays;

class Solution {
    int n;
    int[] nums;
    long[][] memo;
    int MOD = 1_000_000_007;

    public int specialPerm(int[] nums) {
        this.n = nums.length;
        this.nums = nums;
        this.memo = new long[1 << n][n];
        for (long[] row : memo) {
            Arrays.fill(row, -1);
        }

        long totalCount = 0;
        int finalMask = (1 << n) - 1;

        for (int i = 0; i < n; i++) {
            totalCount = (totalCount + solve(finalMask, i)) % MOD;
        }

        return (int) totalCount;
    }

    private long solve(int mask, int lastIdx) {
        // Base case: if only one element is in the permutation, there's one way.
        if (mask == (1 << lastIdx)) {
            return 1;
        }

        if (memo[mask][lastIdx] != -1) {
            return memo[mask][lastIdx];
        }

        long count = 0;
        int prevMask = mask ^ (1 << lastIdx);

        for (int prev = 0; prev < n; prev++) {
            // Check if 'prev' was in the previous sub-permutation
            if ((prevMask & (1 << prev)) != 0) {
                // Check if the current element can follow the previous one
                if (nums[lastIdx] % nums[prev] == 0 || nums[prev] % nums[lastIdx] == 0) {
                    count = (count + solve(prevMask, prev)) % MOD;
                }
            }
        }

        return memo[mask][lastIdx] = count;
    }
}
```
### Algorithm
- This problem can be modeled as finding the number of Hamiltonian paths in a graph where vertices are numbers and an edge exists if one divides the other.
- We use a 2D array `memo[mask][lastIdx]` for memoization. `mask` is a bitmask representing the set of used numbers, and `lastIdx` is the index of the last number in the partial permutation.
- `memo[mask][lastIdx]` stores the number of special permutations using numbers in `mask` and ending with `nums[lastIdx]`.
- Define a recursive function `solve(mask, lastIdx)`:
  - **Base Case:** If `mask` has only one bit set (i.e., `mask == (1 << lastIdx)`), it's a permutation of length 1. Return 1.
  - **Memoization:** If `memo[mask][lastIdx]` is already computed, return the stored value.
  - **Recursive Step:** Calculate the mask for the subproblem: `prevMask = mask ^ (1 << lastIdx)`. Iterate through all possible previous elements `nums[prev]` (where `prev` is from 0 to `n-1`).
  - If `nums[prev]` is in `prevMask` and satisfies the divisibility condition with `nums[lastIdx]`, recursively call `solve(prevMask, prev)` and add the result to a running total (with modulo).
  - Store the computed total in `memo[mask][lastIdx]` and return it.
- The final answer is the sum of `solve((1 << n) - 1, i)` for all `i` from 0 to `n-1`, as any number can be the last element of a full permutation.

# Solutions
### Java

```java
class Solution {
public
  int specialPerm(int[] nums) {
    final int mod = (int)1 e9 + 7;
    int n = nums.length;
    int m = 1 << n;
    int[][] f = new int[m][n];
    for (int i = 1; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if ((i >> j & 1) == 1) {
          int ii = i ^ (1 << j);
          if (ii == 0) {
            f[i][j] = 1;
            continue;
          }
          for (int k = 0; k < n; ++k) {
            if (nums[j] % nums[k] == 0 || nums[k] % nums[j] == 0) {
              f[i][j] = (f[i][j] + f[ii][k]) % mod;
            }
          }
        }
      }
    }
    int ans = 0;
    for (int x : f[m - 1]) {
      ans = (ans + x) % mod;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int specialPerm(vector<int> &nums) {
    const int mod = 1e9 + 7;
    int n = nums.size();
    int m = 1 << n;
    int f[m][n];
    memset(f, 0, sizeof(f));
    for (int i = 1; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if ((i >> j & 1) == 1) {
          int ii = i ^ (1 << j);
          if (ii == 0) {
            f[i][j] = 1;
            continue;
          }
          for (int k = 0; k < n; ++k) {
            if (nums[j] % nums[k] == 0 || nums[k] % nums[j] == 0) {
              f[i][j] = (f[i][j] + f[ii][k]) % mod;
            }
          }
        }
      }
    }
    int ans = 0;
    for (int x : f[m - 1]) {
      ans = (ans + x) % mod;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def specialPerm(self, nums: List[int]) -> int: mod = 10 ** 9 + 7 n = len(nums) m = 1 << n f = [[0] * n for _ in range(m)] for i in range(1, m): for j, x in enumerate(nums): if i >> j & 1: ii = i ^ (1 << j) if ii == 0: f[i][j] = 1 continue for k, y in enumerate(nums): if x % y == 0 or y % x == 0: f[i][j] = (f[i][j] + f[ii][k]) % mod return sum(f[- 1]) % mod

```