The power of pruning in backtracking III

Interesting problem, you run into TLE if you wait to check the conditions after each permutation is generated. Instead, check as the permutation is being built. Code is down below, cheers, ACC.

2992. Number of Self-Divisible Permutations

Medium

Given an integer n, return the number of permutations of the 1-indexed array nums = [1, 2, ..., n], such that it's self-divisible.

Array nums is self-divisible if for every 1 <= i <= n, at least one of the following conditions holds:

• nums[i] % i == 0
• i % nums[i] == 0

A permutation of an array is a rearrangement of the elements of that array, for example here are all of the permutations of the array [1, 2, 3]:

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

 

Example 1:

Input: n = 1
Output: 1
Explanation: The array [1] has only 1 permutation which is self-divisible.

Example 2:

Input: n = 2
Output: 2
Explanation: The array [1,2] has 2 permutations both of which are self-divisible:
nums = [1,2]: This is self-divisible since nums[1] % 1 == 0 and nums[2] % 2 == 0.
nums = [2,1]: This is self-divisible since nums[1] % 1 == 0 and 2 % nums[2] == 0.

Example 3:

Input: n = 3
Output: 3
Explanation: The array [1,2,3] has 3 self-divisble permutations: [1,2,3], [2,1,3], [3,2,1].
It can be shown that the other 3 permutations are not self-divisible. Hence the answer is 3.

 

Constraints:

• 1 <= n <= 15

Accepted

199

Submissions

214

public int SelfDivisiblePermutationCount(int n)
{
    int[] perm = new int[n];
    int retVal = 0;
    SelfDivisiblePermutationCount(0, n, new Hashtable(), ref perm, ref retVal);
    return retVal;
}

private void SelfDivisiblePermutationCount(int index,
                                            int n,
                                            Hashtable used,
                                            ref int[] perm,
                                            ref int retVal)
{
    if (index >= n)
    {
        retVal++;
        return;
    }

    for (int i = 1; i <= n; i++)
    {
        if (!used.ContainsKey(i) && (i % (index + 1) == 0 || (index + 1) % i == 0))
        {
            used.Add(i, true);
            perm[index] = i;
            SelfDivisiblePermutationCount(index + 1, n, used, ref perm, ref retVal);
            used.Remove(i);
        }
    }
}