Hard Leetcode Problem: Number of Squareful Arrays

Here is a hard Leetcode problem: https://leetcode.com/problems/number-of-squareful-arrays/description/

Given an array A of non-negative integers, the array is squareful if for every pair of adjacent elements, their sum is a perfect square.

Return the number of permutations of A that are squareful.  Two permutations A1 and A2 differ if and only if there is some index isuch that A1[i] != A2[i].

Example 1:

Input: [1,17,8]
Output: 2
Explanation: 
[1,8,17] and [17,8,1] are the valid permutations.

Example 2:

Input: [2,2,2]
Output: 1

Note:

1. 1 <= A.length <= 12
2. 0 <= A[i] <= 1e9

The array length is very small (12), which allows us to think about a brute-force solution, which is what's done on the post, but I'm sure there is a DP solution too.
The brute-force solution goes like this:

1. Pre-compute a hash table with the A[i]+A[j] that are perfect square. Do this in 144 steps (fast)
2. Do a DFS but only calling recursively when the condition is satisfied. In other words, don't check the condition after the combination has been created, but rather check it as you're building the permutation

That should do it. Code is below. Cheers, ACC.

public class Solution
{
 public int NumSquarefulPerms(int[] A)
 {
  Hashtable squares = new Hashtable();

  for (int i = 0; i < A.Length; i++)
  {
   for (int j = i + 1; j < A.Length; j++)
   {
    if (!squares.ContainsKey(A[i] + A[j]))
    {
     double sqrt = Math.Sqrt(A[i] + A[j]);
     squares.Add(A[i] + A[j], ((int)sqrt * (int)sqrt) == A[i] + A[j]);
    }
   }
  }

  int num = 0;
  NumSquarefulPerms(A, 0, -1, new Hashtable(), squares, ref num);
  return num;
 }

 private void NumSquarefulPerms(int[] A,
         int index,
         int previousVal,
         Hashtable usedIndex,
         Hashtable squares,
         ref int num)
 {
  if (index >= A.Length)
  {
   num++;
   return;
  }

  Hashtable usedVal = new Hashtable();
  for (int i = 0; i < A.Length; i++)
  {
   if (!usedVal.ContainsKey(A[i]) &&
    !usedIndex.ContainsKey(i) &&
    (index == 0 || (bool)squares[previousVal + A[i]]))
   {
    usedVal.Add(A[i], true);
    usedIndex.Add(i, true);
    NumSquarefulPerms(A, index + 1, A[i], usedIndex, squares, ref num);
    usedIndex.Remove(i);
   }
  }
 }
}