# Easy Python, ~230ms

• My `X` is the set of still available numbers. Gets accepted in about 230 ms:

``````def countArrangement(self, N):
def count(i, X):
if i == 1:
return 1
return sum(count(i - 1, X - {x})
for x in X
if x % i == 0 or i % x == 0)
return count(N, set(range(1, N + 1)))
``````

Note that my `i` goes downwards, from N to 1. Because position `i = 1` can hold any number, so I don't even have to check whether the last remaining number fits there. Also, position `i = 2` happily holds every second number and `i = 3` happily holds every third number, so filling the lowest positions last has a relatively high chance of success. In other words, it's relatively hard to end up with dead ends this way.

If I go upwards (from 1 to N), it takes about 2300 ms:

``````def countArrangement(self, N):
def count(i, X):
if i > N:
return 1
return sum(count(i + 1, X - {x})
for x in X
if x % i == 0 or i % x == 0)
return count(1, set(range(1, N + 1)))``````

• @StefanPochmann if you save your pre-compute result, the runtime can be further reduced to within 100ms. I passed with 92ms.

• @zhongyuan9817 Do you mean what I described here?

• @StefanPochmann

No, I don't like this solution, since we can always find a way to cheat. lol

I mean you can do memorisation, your recursive call is repeating the same task, such as when N = 6, you are recomputing
i = 3, X = (3, 4, 6)
i = 2, X = (4, 6)
...
When N become bigger, the cost could be quit big.

• @StefanPochmann

Just tried to use global cache, the run time has reduced to 66ms.

• @zhongyuan9817 Could you post your code? My following takes a little over 100 ms (got 105, 102, 109, 102 and 112 in five attempts):

``````def countArrangement(self, N):
def count(i, X, memo={}):
if i < 2:
return 1
if X not in memo:
memo[X] = sum(count(i - 1, X - {x})
for x in X
if x % i == 0 or i % x == 0)
return memo[X]
return count(N, frozenset(range(1, N + 1)))``````

• I posted it here, take a look, I believe you can suggest more optimisations.

https://discuss.leetcode.com/topic/79974/python-recursion-dp-66ms

• @StefanPochmann I just used a tuple

• @StefanPochmann

I tried to submit my code 5 times, got these

112, 83, 64, 55, 69

• @zhongyuan9817 I just realized I don't need `i` for my memoization, only `X`. Updated my above memoized solution, takes a bit over 100 ms now. Not as fast as yours, but prettier :-)

• @StefanPochmann
I like you solution, very good balance between performance and aesthetic!

• Found the answer I need here. Thanks.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.