Given a positive integer n, find the least number of perfect square numbers (for example,`1, 4, 9, 16, ...`) which sum to n.

Example 1:

Example 2:

classSolution {

var cache= [Int:Int]()

var perfectSquare= [Int]()

funcfindSum(count:Int,num:Int)->Bool {

switch count {

guardlet c= cache[num]else {

}

return c==1

if cache[num]!=nil {

}

for snin perfectSquare {

iffindSum(count: count-1,num: num- sn) {

cache[num]= count

}

}

}

}

funcisPerfectSquare(n:Int)->Bool {

let sqN=Int(sqrt(Double(n)))

return sqN* sqN== n

}

funcnumSquares(_n:Int)->Int {

guard n>0else {

}

for iin1...n {

ifisPerfectSquare(n: i) {

perfectSquare.append(i)

cache[i]=1

}

}

for iin1...n {

iffindSum(count: i,num: n) {

return i

}

}

return n

}

}