Skip to content

2741. Special Permutations 👍

  • Time: $O(n^2 \cdot 2^n)$
  • Space: $O(n2^n)$
 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
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
 public:
  int specialPerm(vector<int>& nums) {
    const int n = nums.size();
    const int maxMask = 1 << n;
    int ans = 0;
    // dp[i][j] := # of special permutations where the previous number is
    // nums[i] and j is the used nums in mask
    dp.resize(n, vector<int>(maxMask));

    for (int i = 0; i < n; ++i) {
      ans += specialPerm(nums, i, 1 << i, maxMask);
      ans %= kMod;
    }

    return ans;
  }

 private:
  static constexpr int kMod = 1'000'000'007;
  vector<vector<int>> dp;

  int specialPerm(const vector<int>& nums, int prev, int mask,
                  const int& maxMask) {
    if (mask == maxMask - 1)
      return 1;
    if (dp[prev][mask] > 0)
      return dp[prev][mask];

    int res = 0;

    for (int i = 0; i < nums.size(); ++i) {
      if (mask >> i & 1)
        continue;
      if (nums[i] % nums[prev] == 0 || nums[prev] % nums[i] == 0) {
        res += specialPerm(nums, i, mask | 1 << i, maxMask);
        res %= kMod;
      }
    }

    return dp[prev][mask] = res;
  }
};

 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
31
32
33
34
35
36
37
38
class Solution {
  public int specialPerm(int[] nums) {
    final int n = nums.length;
    final int maxMask = 1 << n;
    int ans = 0;
    dp = new int[n][maxMask];

    for (int i = 0; i < n; ++i) {
      ans += specialPerm(nums, i, 1 << i, maxMask);
      ans %= kMod;
    }

    return ans;
  }

  private static final int kMod = 1_000_000_007;
  private int[][] dp;

  private int specialPerm(int[] nums, int prev, int mask, int maxMask) {
    if (mask == maxMask - 1)
      return 1;
    if (dp[prev][mask] != 0)
      return dp[prev][mask];

    int res = 0;

    for (int i = 0; i < nums.length; ++i) {
      if ((mask >> i & 1) == 1)
        continue;
      if (nums[i] % nums[prev] == 0 || nums[prev] % nums[i] == 0) {
        res += specialPerm(nums, i, mask | 1 << i, maxMask);
        res %= kMod;
      }
    }

    return dp[prev][mask] = res;
  }
}

 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
class Solution:
  def specialPerm(self, nums: List[int]) -> int:
    kMod = 1_000_000_007
    maxMask = 1 << len(nums)

    # dp(i, j) := # of special permutations where the previous number is
    # nums[i] and j is the used nums in mask
    @functools.lru_cache(None)
    def dp(prev: int, mask: int) -> int:
      if mask == maxMask - 1:
        return 1

      res = 0

      for i, num in enumerate(nums):
        if mask >> i & 1:
          continue
        if num % nums[prev] == 0 or nums[prev] % num == 0:
          res += dp(i, mask | 1 << i)
          res %= kMod

      return res

    return sum(dp(i, 1 << i)
               for i in range(len(nums))) % kMod