# Number of Squareful Arrays
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-squareful-arrays)
Canonical: https://scaleengineer.com/dsa/problems/number-of-squareful-arrays
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array, Hash Table
---
## Problem
An array is **squareful** if the sum of every pair of adjacent elements is a **perfect square**.

Given an integer array nums, return _the number of permutations of_ `nums` _that are **squareful**_.

Two permutations `perm1` and `perm2` are different if there is some index `i` such that `perm1[i] != perm2[i]`.

**Example 1:**

**Input:** nums = [1,17,8]
**Output:** 2
**Explanation:** [1,8,17] and [17,8,1] are the valid permutations.

**Example 2:**

**Input:** nums = [2,2,2]
**Output:** 1

**Constraints:**

* `1 <= nums.length <= 12`
* `0 <= nums[i] <= 109`

# Approaches
## Brute-force by Generating All Permutations
This approach generates every unique permutation of the input array `nums`. For each generated permutation, it then checks if it satisfies the "squareful" property. The number of such valid permutations is counted.
**Time:** O(N! * N). Generating all unique permutations of `N` elements takes `O(N! * N)` time. For each of the (up to) `N!` permutations, we perform a check that takes `O(N)` time. This is prohibitively slow for `N=12`. · **Space:** O(N! * N). We need to store all permutations. The recursion depth for generation is `O(N)`, but the storage for the results dominates.
**Pros:** Simple to understand conceptually.
**Cons:** Extremely inefficient in both time and space.; Not feasible for the given constraints (`N` up to 12).
### Explanation
The core of this method is a backtracking algorithm to generate all unique permutations. To handle duplicate numbers in `nums`, the array is first sorted. During backtracking, we add a rule to skip an element if it's the same as the previous one and the previous one hasn't been used in the current path. This ensures each unique permutation is generated only once.
A helper function `isSquareful` iterates through a given permutation and checks if the sum of every adjacent pair of elements is a perfect square. Another helper `isPerfectSquare` checks if a number is a perfect square. The main function orchestrates this: generate all permutations, then loop through them, check each one, and count the valid ones.

```java
// This is a conceptual snippet. A full implementation would be too long and inefficient.
public int numSquarefulPerms(int[] nums) {
    List<List<Integer>> allPermutations = new ArrayList<>();
    // 1. Generate all unique permutations of nums
    // ... (implementation of permutation generation)
    
    int count = 0;
    // 2. Iterate and check each permutation
    for (List<Integer> p : allPermutations) {
        if (isSquareful(p)) {
            count++;
        }
    }
    return count;
}

private boolean isSquareful(List<Integer> p) {
    for (int i = 0; i < p.size() - 1; i++) {
        if (!isPerfectSquare(p.get(i) + p.get(i+1))) {
            return false;
        }
    }
    return true;
}

private boolean isPerfectSquare(int n) {
    if (n < 0) return false;
    int sqrt = (int) Math.sqrt(n);
    return sqrt * sqrt == n;
}
```
### Algorithm
- Define a function to generate all unique permutations of `nums`. This can be done with backtracking. Sort `nums` first to handle duplicates.
- Store all generated unique permutations in a list.
- Initialize a counter `squareful_count` to 0.
- Iterate through each permutation in the list.
- For each permutation, check if it's squareful by iterating from the first to the second-to-last element and verifying that the sum of each adjacent pair is a perfect square.
- If a permutation is squareful, increment `squareful_count`.
- Return `squareful_count`.

## Backtracking with On-the-fly Validation
This approach avoids generating all permutations upfront. Instead, it builds permutations one element at a time using backtracking (DFS). The "squareful" condition is checked as each new element is added. If adding an element violates the condition, that entire branch of the search is pruned, leading to significant performance improvement.
**Time:** O(N!). In the worst-case scenario (where many pairs sum to perfect squares), the algorithm explores a number of paths proportional to `N!`. However, the pruning is very effective in practice, making it much faster than the theoretical worst case. · **Space:** O(N). The space is dominated by the recursion stack depth, which is at most `N`, and the frequency map, which stores at most `N` unique numbers.
**Pros:** Drastically more efficient than brute-force.; Feasible for the given constraints.; Space efficient.
**Cons:** The complexity is still exponential, but this is inherent to permutation-style problems.
### Explanation
We use a recursive DFS function to build the permutations. To handle duplicates efficiently, we first count the frequency of each number in `nums` and store it in a map.
The DFS function explores adding the next number to the current partial permutation. The state of the recursion can be represented by the partial permutation being built.
At each step of the recursion, we iterate through the available numbers (those with a count > 0 in the frequency map).
Before adding a number, we check if it forms a perfect square sum with the last element of the current partial permutation. If it does (or if the permutation is empty), we add the number, decrement its frequency, and recurse.
After the recursive call returns, we backtrack by removing the number and restoring its frequency.
The base case for the recursion is when the permutation's length equals `N`. At this point, we've found a valid squareful permutation, so we increment a global counter.

```java
class Solution {
    int count = 0;
    Map<Integer, Integer> freqMap = new HashMap<>();
    int n;

    public int numSquarefulPerms(int[] nums) {
        this.n = nums.length;
        if (n == 0) return 0;
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }
        dfs(new ArrayList<>());
        return count;
    }

    private void dfs(List<Integer> currentPath) {
        if (currentPath.size() == n) {
            count++;
            return;
        }

        for (int nextNum : freqMap.keySet()) {
            if (freqMap.get(nextNum) > 0) {
                if (currentPath.isEmpty() || isPerfectSquare(currentPath.get(currentPath.size() - 1) + nextNum)) {
                    currentPath.add(nextNum);
                    freqMap.put(nextNum, freqMap.get(nextNum) - 1);
                    
                    dfs(currentPath);
                    
                    freqMap.put(nextNum, freqMap.get(nextNum) + 1);
                    currentPath.remove(currentPath.size() - 1);
                }
            }
        }
    }

    private boolean isPerfectSquare(long num) {
        if (num < 0) return false;
        long sqrt = (long) Math.sqrt(num);
        return sqrt * sqrt == num;
    }
}
```
### Algorithm
- Count the frequencies of each number in `nums` and store them in a hash map.
- Initialize a result counter to 0.
- Implement a recursive backtracking function, say `dfs(path)`.
- Base Case: If `path.size()` equals the total number of elements `N`, a valid permutation is found. Increment the result counter and return.
- Recursive Step: Iterate through each unique number `num` from the frequency map.
- If the count of `num` is greater than 0:
    a. Check if the path is empty or if `path.getLast() + num` is a perfect square.
    b. If the condition holds, add `num` to the path, decrement its count in the map, and make a recursive call: `dfs(path)`.
    c. Backtrack: After the call returns, remove `num` from the path and restore its count in the map.
- Start the process by calling `dfs` with an empty path.
- Return the result counter.

## Graph Traversal on a Pre-computed Adjacency Graph
This approach models the problem as finding the number of Hamiltonian paths in a graph. The unique numbers from the input array are the vertices. An edge exists between two vertices if their sum is a perfect square. The problem then becomes counting paths of length `N` that visit each number according to its frequency.
**Time:** O(U^2 + N!). `U` is the number of unique elements. `O(U^2)` is for building the graph. The search part is `O(N!)` in the worst case, but it's faster than the previous approach because at each step, we only iterate over valid neighbors instead of all unique numbers. · **Space:** O(U^2). The space is dominated by the storage for the graph, which can have up to `U^2` edges, where `U` is the number of unique elements. The recursion depth is `O(N)`. Since `U <= N`, this is `O(N^2)`.
**Pros:** Most efficient approach.; Pre-computation prunes the search space more effectively during the DFS.
**Cons:** Slightly more complex to implement due to the explicit graph construction.; Higher space complexity than the simple backtracking if the graph is dense.
### Explanation
First, we pre-process the input. We build a frequency map of the numbers in `nums`.
Then, we construct a graph where vertices are the unique numbers. We iterate through all pairs of unique numbers `(u, v)` and add an edge between them if `u + v` is a perfect square. This graph is stored as an adjacency list.
With the graph and frequencies, we perform a DFS (backtracking search). The search aims to find paths of length `N`.
The DFS function takes the current node `u` and the current path length as arguments.
It explores all neighbors `v` of `u`. If `v` is available (its count in the frequency map is > 0), we "visit" it by decrementing its count, and recurse with `dfs(v, pathLength + 1)`.
After the recursive call, we backtrack by restoring the count of `v`.
The base case is when the path length reaches `N`, at which point we've found a valid Hamiltonian path, and we increment our total count.
To start the search, we iterate through each unique number, treat it as a starting node, and initiate a DFS from it.

```java
class Solution {
    Map<Integer, Integer> freqMap = new HashMap<>();
    Map<Integer, List<Integer>> graph = new HashMap<>();
    int count = 0;
    int n;

    public int numSquarefulPerms(int[] nums) {
        this.n = nums.length;
        if (n == 0) return 0;

        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        for (int u : freqMap.keySet()) {
            graph.put(u, new ArrayList<>());
        }

        for (int u : freqMap.keySet()) {
            for (int v : freqMap.keySet()) {
                if (isPerfectSquare((long)u + v)) {
                    graph.get(u).add(v);
                }
            }
        }

        for (int startNode : freqMap.keySet()) {
            freqMap.put(startNode, freqMap.get(startNode) - 1);
            dfs(startNode, 1);
            freqMap.put(startNode, freqMap.get(startNode) + 1);
        }
        return count;
    }

    private void dfs(int u, int pathLength) {
        if (pathLength == n) {
            count++;
            return;
        }
        for (int v : graph.get(u)) {
            if (freqMap.get(v) > 0) {
                freqMap.put(v, freqMap.get(v) - 1);
                dfs(v, pathLength + 1);
                freqMap.put(v, freqMap.get(v) + 1);
            }
        }
    }

    private boolean isPerfectSquare(long num) {
        if (num < 0) return false;
        long sqrt = (long) Math.sqrt(num);
        return sqrt * sqrt == num;
    }
}
```
### Algorithm
- Create a frequency map of numbers in `nums`.
- Create an adjacency list `graph` where vertices are unique numbers from `nums`.
- For every pair of unique numbers `(u, v)`, if `u + v` is a perfect square, add an edge from `u` to `v` and `v` to `u` in the graph.
- Initialize a result counter to 0.
- Implement a recursive `dfs(node, path_len)` function.
- Base Case: If `path_len == N`, increment the result counter and return.
- Recursive Step: For each neighbor `v` of `node` in the `graph`:
    a. If the count of `v` in the frequency map is > 0:
    b. Decrement the count of `v`, and call `dfs(v, path_len + 1)`.
    c. Backtrack: Increment the count of `v`.
- To start the process, iterate through each unique number `u` as a potential starting node. For each `u`, decrement its count, call `dfs(u, 1)`, and then backtrack by restoring its count.
- Return the result counter.

# Solutions
### Java

```java
class Solution {
public
  int numSquarefulPerms(int[] nums) {
    int n = nums.length;
    int[][] f = new int[1 << n][n];
    for (int j = 0; j < n; ++j) {
      f[1 << j][j] = 1;
    }
    for (int i = 0; i < 1 << n; ++i) {
      for (int j = 0; j < n; ++j) {
        if ((i >> j & 1) == 1) {
          for (int k = 0; k < n; ++k) {
            if ((i >> k & 1) == 1 && k != j) {
              int s = nums[j] + nums[k];
              int t = (int)Math.sqrt(s);
              if (t * t == s) {
                f[i][j] += f[i ^ (1 << j)][k];
              }
            }
          }
        }
      }
    }
    long ans = 0;
    for (int j = 0; j < n; ++j) {
      ans += f[(1 << n) - 1][j];
    }
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int x : nums) {
      cnt.merge(x, 1, Integer : : sum);
    }
    int[] g = new int[13];
    g[0] = 1;
    for (int i = 1; i < 13; ++i) {
      g[i] = g[i - 1] * i;
    }
    for (int v : cnt.values()) {
      ans /= g[v];
    }
    return (int)ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numSquarefulPerms(vector<int> &nums) {
    int n = nums.size();
    int f[1 << n][n];
    memset(f, 0, sizeof(f));
    for (int j = 0; j < n; ++j) {
      f[1 << j][j] = 1;
    }
    for (int i = 0; i < 1 << n; ++i) {
      for (int j = 0; j < n; ++j) {
        if ((i >> j & 1) == 1) {
          for (int k = 0; k < n; ++k) {
            if ((i >> k & 1) == 1 && k != j) {
              int s = nums[j] + nums[k];
              int t = sqrt(s);
              if (t * t == s) {
                f[i][j] += f[i ^ (1 << j)][k];
              }
            }
          }
        }
      }
    }
    long long ans = 0;
    for (int j = 0; j < n; ++j) {
      ans += f[(1 << n) - 1][j];
    }
    unordered_map<int, int> cnt;
    for (int x : nums) {
      ++cnt[x];
    }
    int g[13] = {1};
    for (int i = 1; i < 13; ++i) {
      g[i] = g[i - 1] * i;
    }
    for (auto &[_, v] : cnt) {
      ans /= g[v];
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numSquarefulPerms(self, nums: List[int]) -> int: n = len(nums) f = [[0] * n for _ in range(1 << n)] for j in range(n): f[1 << j][j] = 1 for i in range(1 << n): for j in range(n): if i >> j & 1: for k in range(n): if (i >> k & 1) and k != j: s = nums[j] + nums[k] t = int(sqrt(s)) if t * t == s: f[i][j] += f[i ^ (1 << j)][k] ans = sum(f[(1 << n) - 1][j] for j in range(n)) for v in Counter(nums). values(): ans //= factorial(v) return ans

```