# Python weird but not too bad DFS

• I have read the DP, BFS, and Math solutions, but I went through the discussion and didn't see DFS as the mainstream solution, so just sharing for your interest.

'''

``````def numSquares(self, n):

self.r = sys.maxint
self.n = n
return self.recursion(n, int(n ** 0.5), 0)

def recursion(self, n, s, prev_num):

if n == 0:
return 0

res = sys.maxint

for i in range(s, 0, -1):

i_square = i ** 2
num, rest = n / i_square, n % i_square

if num + prev_num > self.r:
break

res = min(res, num + self.recursion(rest, int(rest ** 0.5), prev_num + num))

if n == self.n:
self.r = min(self.r, res)

return res
``````

'''
My idea is simple:
For n, i start with sqrt(n), and do a DFS on n % (i ** 2).
At the beginning, I got TLE without (Of course)

'''

``````if num + cur_num > self.r:
break
``````

'''
Then I just added the restriction, if DFS goes more steps than the current minimum result, stop.

I know the math solution's performance beats this dummy's ass off, but I am just sharing it for your reference.
It is not too bad though, beating 70%, around 400 ms for Python.

And there are lots of room to make improvement, like the for loop doesn't necessarily need to go to 0, etc.

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