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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Bit manipulation

Data structures

Complete search

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

Solutions:
class Solution:

	def countArrangement(self, N):
		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):
		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):
		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):
		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))
			cache[key] = total
			return total
		return helper(N, tuple(range(1, N + 1)))