Why I am getting absurd values on using maximum integer value?

for (Integer square : squares) {
    if (square>k)
        break;
    ...
}

This loop expects the squares to be iterated over from smallest to largest. The problem is that a HashSet doesn't have a predictable order. If a large square is encountered early then the loop breaks before considering all of the other smaller squares.

To ensure order you need to use a SortedSet. Switching to a TreeSet fixes the program:

squares = new TreeSet<>();

Side note, I strongly suggest you add more memoization. When n grows there are a lot of repeated calls to getSteps for the same values. You'll get a substantial speed up if you have getSteps cache its return values for each k and consult the cache when it's called before it goes into the expensive loop.

Overflow!

The error starts happening if the value to compute is >=17.

Your result is -2147483648 which is....yep, Integer.MAX_VALUE+1

In the recursive operation number t+1:

 for (Integer square : squares) {
      if (square>k)
           break;
    cur = getSteps(k-square) + 1;
    min = Math.min(cur, min);
 }
return min;

cur overflows as in the operation number t, min was returned, with a value of Integer.MAX_VALUE.

This makes

cur = Integer.MAX_VALUE + 1 // --> -2147483648

From there, Math.min(cur,min) has found its final value: -2147483648

This only happens once, that's why if you set Integer.MAX_VALUE-1 as min, doesn't fail as it won't overflow (and won't be selected as the minimum value neither).

Cheap workaround: long

If you need/wish to maintain that code, this would be a workaround.

Nope, just don't do this. As John comments below, this just makes the failure less aparent

His answer was the correct solution from the beginning

Preserve the insertion order

The insertion order must be respected when retrieving the squares. That's the key here, as John correctly states. There are two type of sets that honor this: LinkedHashSet and TreeSet.

Both are bad for this scenario, but specifically TreeSet is just terrible.

For TreeSet, add, contains and remove mean ~O(log(N)). No joke here, just test it executing numSquares(99). It's a low number, but I noticed the time grew exponentially after certain values (55-60). So 99 is more than enough to confirm this.

I waited for 3 hours (for real) and that thing didn't finish. It makes you believe your computer's processing capacity is lower than a one of those mid 90's LCD videoconsoles.

This was also correctly pointed out by John's answer.

My best try

After testing, the best performance was the code with a mixed approach that used a HashSet and an ArrayList. The mechanism can be resumed in:

• Add the elements to the ArrayList (it will respect insertion order)
• Invoke HashSet.addAll(ArrayList)
• HashSet.contains is the condition check
• for (Integer square : ArrayList) is the loop mechanism

This is the code:

 Set<Integer> sqSet;  
 List<Integer> sqArr;
 //...
 public int numSquares(int n)
 {
     sqSet = new HashSet<>((n/10)+2);
     sqArr = new ArrayList<>((n/10)+2);  //avoids grow()

     for (int i=1; i*i<=n; i++)
         sqArr.add(i*i);
    
     sqSet.addAll(sqArr);
     return getSteps(n);
 }

 public int getSteps(int k) 
 {
    if (sqSet.contains(k))
       return 1;
    int min=Integer.MAX_VALUE;
    int cur;
    for (Integer square : sqArr) 
    { 
       if (square>k)
         break;
       cur = getSteps(k-square) + 1;
       min = Math.min(cur, min);
     }   
     return min;
  }