Readme

996.Number-of-Squareful-Arrays

此题可以理解成一张图的路径搜索问题。我们提前处理所有的pair，对于相加是平方数的两个元素，我们就认为它们之间有一条边。我们的任务就是找出所有的路径，能够走遍所有的点。

考虑到题目需要穷举所有的路径，并且数据规模异常得小，大概率这是一个NP问题，可以用暴力的深度搜索，和473，698都很相似。这类题目都需要用visited来记录已经访问过的元素来避免重复。

特别注意的是，本题要求避免“长得一样”的重复路径，需要有剪支的操作。比如对于数列1,2,2,2,3,4,我们想取不重复的permutation。当我们考察完1,2,X,X,X,X之后，需要回溯考虑第二个元素的其他候选。我们发现，如果第二个位置再选其他的“2”，就会又完全重复之前的搜索。尽管是两个不同的“2”，但这样的两条路径被认为是重复。为了剪枝，我们在从cur开始寻找下一层深度的节点时，可以将所有的候选节点事先排个序，如果候选节点B和它之前考察过的候选节点A相同，那么我们就略过对候选节点B的考察。

另外一个细节就是如何判断一个数是否是平方数？正确的做法是if (sqrt(x)==(int)sqrt(x))

Leetcode Link