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 ith 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.