<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:
    int numSquarefulPerms(vector<int>& nums) {
        perms_ = 0;
        N = nums.size();
        egress_ = unordered_map<int, unordered_set<int>>{};
        count_ = unordered_map<int, int>{};
        unordered_set<int> uniqued;

        // 1. Build graph adjacency list representation
        for (int i = 0; i < N; i++) {
            count_[nums[i]]++;
            uniqued.insert(nums[i]);
            for (int j = i + 1; j < N; j++) {
                int sum = nums[i] + nums[j];
                int root = sqrt(sum);

                if (root * root != sum) continue;

                egress_[nums[i]].insert(nums[j]);
                egress_[nums[j]].insert(nums[i]);
            }
        }

        // for (const auto [key, val] : egress_) {
        //     cout << key << "[ ";
        //     for (const auto e : val) cout << e << " ";
        //     cout << "]" << endl;
        // }

        // for (const auto [key, val] : count_) {
        //     cout << key << " count:" << val << endl;
        // }

        // cout << "uniqued: ";
        // for (const auto u : uniqued) cout << u << " ";
        // cout << endl;

        // 2. Start with every num, DFS find permutation (exhaust all nums)
        for (const auto num : uniqued) {
            DFS(num, 1);
        }

        return perms_;
    }

private:
    void DFS(int num, int used) {
        if (count_[num] == 0) return;
        if (used == N) perms_++;

        count_[num]--;
        // cout << num << " used:" << used << endl;

        int last = -1;
        for (const auto egress : egress_[num]) {
            if (last != -1 && egress == last) continue;
            DFS(egress, used + 1);
            last = egress;
        }

        count_[num]++;
    }

    int perms_;
    size_t N;
    unordered_map<int, unordered_set<int>> egress_;
    unordered_map<int, int> count_;
};
10400