# Recursive DFS Solution in Java which I believe has O(n) run-time

• public class Solution {

``````public int numSquares(int n) {
return dfs(n,0,n);
}

public int dfs(int n, int level, int min) {
if(n == 0 || level >= min) return level;
for(int i = (int) Math.sqrt(n); i > 0; i--) {
min = dfs(n - ((int)Math.pow(i,2)), level+1, min);
}
return min;
}
``````

}

I'm not certain on my math so please correct me if I'm wrong, but the run-time should be O(n^(1/2) * n^(1/4) * n^(1/8) * ...), repeating as many times as there are layers in the minimum, which regardless of the number of layers approaches O(n).

• `((int)Math.pow(i,2))` is an awful waste to say `i*i` ;)

• I'd like to see a detailed runtime analysis for this if anyone knows one, as it highly depends on what's the most trivial perfect square sum for the input (first DFS result where `n==0`): `a*biggest_square + b*smaller_square + c*other_smaller_square ...`, for example for `48=36+9+1+1+1`. Here're the number of `dfs` calls for a few inputs:

``````n		dfs		dfs-for
48		208		59
49		8		1
100		11		1
200		159		15
300		3011	324
400		21		1
500		396		23
600		7755	532
1000	1174	149
2000	1574	45
5000	3927	71
10000	101		1
100000	78550	317
``````

`dfs` column is the number of entries
`dfs-for` column is the number of calls that don't get cut off by the guard

When I say highly depends I mean highly: `10000000` runs in 22ms, but `99999` is TLE. The verifier fails to finish for some numbers that this algorithm handles with ease and vice versa.

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