Skip to content

2992. Number of Self-Divisible Permutations 👍

  • Time: $O(n \cdot 2^n)$
  • Space: $O(2^n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int selfDivisiblePermutationCount(int n) {
    return dfs(1, /*used=*/0, n);
  }

 private:
  int dfs(int num, int used, int n) {
    if (num > n)
      return 1;

    int count = 0;
    for (int i = 1; i <= n; ++i)
      if ((used >> i & 1) == 0 && (num % i == 0 || i % num == 0))
        count += dfs(num + 1, used | (1 << i), n);

    return count;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public int selfDivisiblePermutationCount(int n) {
    return dfs(1, /*used=*/0, n);
  }

  private int dfs(int num, int used, int n) {
    if (num > n)
      return 1;

    int count = 0;
    for (int i = 1; i <= n; i++)
      if (((used >> i) & 1) == 0 && (num % i == 0 || i % num == 0))
        count += dfs(num + 1, used | (1 << i), n);

    return count;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def selfDivisiblePermutationCount(self, n: int) -> int:
    def dfs(num: int, used: int) -> int:
      if num > n:
        return 1

      count = 0
      for i in range(1, n + 1):
        if (used >> i & 1) == 0 and (num % i == 0 or i % num == 0):
          count += dfs(num + 1, used | 1 << i)

      return count

    return dfs(1, 0)