class Solution {

    boolean perfSum(int val){
        int sqrt = (int)Math.sqrt(val);
        return sqrt*sqrt == val;
    }

    public int numSquarefulPerms(int[] a) {
        return count(a, -1, 0);
    }

    int count(int[] a, int prevIndex, int visited){
        if(visited == (1<<(a.length)) - 1){
            return 1;
        }else{
            int result = 0;
            Set<Integer> checked = new HashSet<>();
           for(int i=0;i<a.length;++i){
               if((visited&(1<<i))==0 && !checked.contains(a[i])&& (prevIndex==-1 || perfSum(a[prevIndex] + a[i]))){
                        checked.add(a[i]);
                        result += count(a, i, visited|(1<<i));
               }
           }

            return result;
        }
    }
}