<p>An array is <strong>squareful</strong> if the sum of every pair of adjacent elements is a <strong>perfect square</strong>.</p>

<p>Given an integer array nums, return <em>the number of permutations of </em><code>nums</code><em> that are <strong>squareful</strong></em>.</p>

<p>Two permutations <code>perm1</code> and <code>perm2</code> are different if there is some index <code>i</code> such that <code>perm1[i] != perm2[i]</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,17,8]
<strong>Output:</strong> 2
<strong>Explanation:</strong> [1,8,17] and [17,8,1] are the valid permutations.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,2,2]
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 12</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution {
public:
    unordered_set<string> ansPaths;
    vector<vector<int>> sumArray;
    int n, ans;

    bool isPerfectSquare(int num) {
        int temp = sqrt(num);
        return (temp * temp == num);
    }

    void traverse(vector<int>& nums, string curPath, int idx, unordered_set<int> visited) {
        visited.insert(idx);

        if (visited.size() == n) {
            ansPaths.insert(curPath);
            return;
        }

        vector<int> nextIndicies;

        for(int i = 0; i < n; i++) {
            if (visited.count(i) > 0) continue;

            if (i != idx && isPerfectSquare(sumArray[i][idx])) {
                nextIndicies.push_back(i);
            }
        }

        set<int> seenNumbers;

        for(int i = 0; i < nextIndicies.size(); i++) {
            if (seenNumbers.count(nums[nextIndicies[i]]) == 0) {
                seenNumbers.insert(nums[nextIndicies[i]]);
                string tempPath = curPath + "," + to_string(nums[nextIndicies[i]]);
                traverse(nums, tempPath, nextIndicies[i], visited);
            }
        }
    }

    int numSquarefulPerms(vector<int>& nums) {
        n = nums.size();

        for(int i = 0; i < n; i++) {
            vector<int> temp;

            for(int j = 0; j < n; j++) {
                temp.push_back(nums[i] + nums[j]);
            }

            sumArray.push_back(temp);
        }

        for(int i = 0; i < n; i++) {
            unordered_set<int> visited;
            string curPath = to_string(nums[i]);
            traverse(nums, curPath, i, visited);
        }

        return ansPaths.size();
    }
};

/*
Start at a perfect square node in 2d sum array
Pick a direction, vertical or horizontal and find the next perfect square node
Keep track of unique paths, use a string formatted set?

[1,17,8]

1 8 17 -> 9 = 3 * 3, 25 = 5 * 5
17 8 1 -> 25, 9


   1 17 8
1  -  18 9
17 18 - 25
8. 9  25 -

1 8 17
17 8 1

*/
15500