# 16 lines Python Naive DFS

• ``````class Solution(object):
def numberOfPatterns(self, m, n):
visited = {}
ret = [0]
self.dfsHelper(ret, visited, 0, m, n, -9)
return ret[0]

def dfsHelper(self, ret, visited, res, m, n, prev):
if m <= res <= n:
ret[0] += 1
if res == n:
return
for i in xrange(1, 10):
if i not in visited:
x, y, xp, yp = (i - 1) / 3, (i - 1) % 3, (prev - 1) / 3, (prev - 1) % 3
if (5 not in visited and abs(xp - x) == 2 and abs(yp - y) == 2) or ((yp == y and abs(xp - x) == 2) or (xp == x and abs(yp - y) == 2)) and (prev + i) / 2 not in visited:
continue
visited[i] = 1
self.dfsHelper(ret, visited, res + 1, m, n, i)
del visited[i]``````

• @jedihy

Not naive. Instead I think it's straightforward.

Can you think of an iterative solution?

• No, I can't unless I translate the recursive code to iterative one by using stack which makes no sense.

• @jedihy

Yes it makes sense.
Actually, if you were to translate it into iterative solution, you would probably get MLE...
Which is why I think the memory limit is too restricted for python non-recursive solutions.

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