Solution
Approach 1: Backtracking
Intuition
Construct a graph where an edge from to exists if is a perfect square. Our goal is to investigate Hamiltonian paths of this graph: paths that visit all the nodes exactly once.
Algorithm
Let's keep a current count
of what values of nodes are left to visit, and a count todo
of how many nodes left to visit.
From each node, we can explore all neighboring nodes (by value, which reduces the complexity blowup).
Please see the inline comments for more details.
Complexity Analysis

Time Complexity: , where is length of
A
. A tighter bound is outside the scope of this article. However, it can be shown that the underlying graph is triangle free, as well as other properties that would dramatically shrink this complexity. 
Space Complexity: .
Approach 2: Dynamic Programming
Intuition
As in Approach 1, construct an underlying graph. Since the number of nodes is small, we can use dynamic programming with a 'visited' mask.
Algorithm
We construct the graph in the same method as in Approach 1.
Now, let dfs(node, visited)
be the number of ways from node
to visit the remaining unvisited nodes. Here, visited
is a mask: (visited >> i) & 1
is true if and only if the i
th node has been visited.
Afterwards, we may have overcounted if there are repeated values in A
. To account for this, for every x
in A
, if A
contains x
a total of k
times, we divide the answer by k!
.
Complexity Analysis

Time Complexity: , where is length of
A
. 
Space Complexity: .
Analysis written by: @awice.