解决方案


方法一:回溯

思路

构造一张图,包含所有的边 ,如果满足 是一个完全平方数。我们的目标就是求这张图的所有哈密尔顿路径,即经过图中所有点仅一次的路径。

算法

我们使用 count 记录对于每一种值还有多少个节点等待被访问,与一个变量 todo 记录还剩多少个节点等待被访问。

对于每一个节点,我们可以访问它的所有邻居节点(从数值的角度来看,从而大大减少复杂度)。

对于每一个节点,我们可以访问它的所有邻居节点(从数值的角度来看,从而大大减少复杂度)。

更多细节请看行内注释。

复杂度分析

  • 时间复杂度: ,其中 A 的长度。更加严格的复杂度界限在本文中不做赘述。 但是明显构造得到的图中不包含三角形,且图的另外一些性质保证了算法的复杂度。

  • 空间复杂度:


方法二:动态规划

思路

方法一 中相似,构造一样的图。因为节点的数量非常少,所以可以使用掩码标记所有已经过点的方式来进行动态规划。

算法

我们用同样的方式构造与 方法一 中一样的图。

现在,我们令 dfs(node, visited) 等于从 node 节点出发访问剩余的节点的可行方法数。这里,visited 是一个掩码:(visited >> i) & 1 为真,当且仅当第 i 个节点已经被访问过了。

这样计算之后,对于 A 中拥有相同值的节点我们会重复计算。考虑这个因素,对于 A 中的值 x,如果 A 中包含 k 个值为 x 的节点,我们令最终答案除以 k!

复杂度分析

  • 时间复杂度: ,其中 A 的长度。

  • 空间复杂度: