//Very very poor technique.. there must be a better way..
import java.util.*;
public class HipToBeSquare
{
        
        public static boolean isSquared(int x, int y, ArrayList tried){
              //System.out.printf("%d, %d%n", x, y);
              if (y == 0) return false;
              if (tried.contains(y)) return false;
              tried.add(y);
              if (x - y * y == 0){
                  return true;
                }
              int newNumber = (x - y * y);
              
              boolean worked = isSquared(newNumber, highestSquare(newNumber), tried);
              if (worked == false){
                  tried.remove(tried.indexOf(y));
                  return isSquared(x, y - 1, tried);
                }
            else{
                //System.out.println("Got here..");   
                return true;
            }
            
            }
        
        public static boolean inTried(int[]tried, int n){
            for(int i: tried){
                if (i == n) return true;
                if (i == 101) return false;
            }
            return false; //SHOULD NOT REACH THIS!
        }
            
        public static void addTried(int[] tried, int n){
            for(int i = 0; i < 100; i++){
                if (tried[i] == 101) {
                    tried[i] = n;
                    break;
                }
            }
        }
        public static int highestSquare(int x){
            for (int i = 1; i <= 100; i++){
            if (x >= i * i) 
                continue;
            else
                return i - 1;
            }
            return 0;
        }
        public static void main(String args[]){
            Scanner reader = new Scanner(System.in);
            System.out.print("Enter a number: ");
            int number = reader.nextInt();
            ArrayList tried = new ArrayList();
            System.out.println(isSquared(number, highestSquare(number), tried));
            System.out.println(tried);
        
    }
}