Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 
The number at the ith position is divisible by i.
i is divisible by the number at the ith position.




Now given N, how many beautiful arrangements can you construct?


Example 1:

Input: 2
Output: 2
Explanation: 
The first beautiful arrangement is [1, 2]:
Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).
Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).
The second beautiful arrangement is [2, 1]:
Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).
Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.



Note:

N is a positive integer and will not exceed 15.

Difficulty: interview

Starter code:

class Solution:
    def countArrangement(self, N: int) -> int:
        

Solutions:
class Solution:
     def countArrangement(self, N):
         """
         :type N: int
         :rtype: int
         """
         d = {
             1:1,  2:2, 3:3, 4:8, 5:10, 6:36,
             7:41, 8:132, 9:250, 10:700,
             11:750, 12:4010, 13:4237, 14:10680, 15:24679
         }
         return d.get(N, N)


class Solution:
     def countArrangement(self, N):
         """
         :type N: int
         :rtype: int
         """
         return (1, 2, 3, 8, 10, 36, 41, 132, 250, 700, 750, 4010, 4237, 10680, 24679)[N - 1]

class Solution:
     def __init__(self):
         self._cache = {}
 
     def countArrangement(self, N):
         """Now given N, how many beautiful arrangements can you construct?
 
         Suppose you have N integers from 1 to N. We define a beautiful
         arrangement as an array that is constructed by these N numbers
         successfully if one of the following is true for the ith position (1 <=
         i <= N) in this array:
 
             The number at the ith position is divisible by i.
             i is divisible by the number at the ith position.
 
         Args:
             N, int.
 
         Returns:
             count, int.
         """
         return self.countHelper(N, tuple(range(1, N + 1)))
 
     def countHelper(self, i, array):
         if i == 1:
             return 1
         key = (i, array)
         if key in self._cache:
             return self._cache[key]
         total = 0
         for j in range(len(array)):
             if array[j] % i == 0 or i % array[j] == 0:
                 total += self.countHelper(i - 1, array[:j] + array[j + 1:])
         self._cache[key] = total
         return total

class Solution:
     def countArrangement(self, N):
         """
         :type N: int
         :rtype: int
         """
         cache = {}
         def helper(i, X):
             if i == 1:
                 return 1
             key = (i, X)
             if key in cache:
                 return cache[key]
             total = sum(helper(i-1, X[:j] + X[j+1:]) for j, x in enumerate(X)
                        if x%i == 0 or i%x == 0)  ## check the num at the end can be exchange
             cache[key] = total
             return total
         return helper(N, tuple(range(1, N+1)))