from math import isqrt
from collections import Counter
def numSquarefulPerms(A):
def is_square(num):
root = isqrt(num)
return root * root == num
def dfs(x, count, length):
if length == len(A):
return 1
total = 0
for y in graph[x]:
if count[y]:
count[y] -= 1
total += dfs(y, count, length + 1)
count[y] += 1
return total
A.sort()
graph = {x: [] for x in A}
for i, x in enumerate(A):
for j, y in enumerate(A):
if i != j and is_square(x + y):
graph[x].append(y)
count = Counter(A)
res = 0
for x in count:
count[x] -= 1
res += dfs(x, count, 1)
count[x] += 1
return res
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <cmath>
using namespace std;
class Solution {
public:
int numSquarefulPerms(vector<int>& A) {
unordered_map<int, vector<int>> graph;
int n = A.size();
sort(A.begin(), A.end());
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i != j && isSquare(A[i] + A[j])) {
graph[A[i]].push_back(A[j]);
}
}
}
unordered_map<int, int> count;
for (int x : A) count[x]++;
int res = 0;
for (auto& p : count) {
count[p.first]--;
res += dfs(p.first, count, graph, 1, n);
count[p.first]++;
}
return res;
}
private:
bool isSquare(int num) {
int root = sqrt(num);
return root * root == num;
}
int dfs(int x, unordered_map<int, int>& count, unordered_map<int, vector<int>>& graph, int length, int n) {
if (length == n) return 1;
int total = 0;
for (int y : graph[x]) {
if (count[y]) {
count[y]--;
total += dfs(y, count, graph, length + 1, n);
count[y]++;
}
}
return total;
}
};
import java.util.*;
class Solution {
public int numSquarefulPerms(int[] A) {
Map<Integer, List<Integer>> graph = new HashMap<>();
Arrays.sort(A);
int n = A.length;
for (int x : A) graph.put(x, new ArrayList<>());
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i != j && isSquare(A[i] + A[j])) {
graph.get(A[i]).add(A[j]);
}
}
}
Map<Integer, Integer> count = new HashMap<>();
for (int x : A) count.put(x, count.getOrDefault(x, 0) + 1);
int res = 0;
for (int x : count.keySet()) {
count.put(x, count.get(x) - 1);
res += dfs(x, count, graph, 1, n);
count.put(x, count.get(x) + 1);
}
return res;
}
private boolean isSquare(int num) {
int root = (int)Math.sqrt(num);
return root * root == num;
}
private int dfs(int x, Map<Integer, Integer> count, Map<Integer, List<Integer>> graph, int length, int n) {
if (length == n) return 1;
int total = 0;
for (int y : graph.get(x)) {
if (count.get(y) != null && count.get(y) > 0) {
count.put(y, count.get(y) - 1);
total += dfs(y, count, graph, length + 1, n);
count.put(y, count.get(y) + 1);
}
}
return total;
}
}
function numSquarefulPerms(A) {
function isSquare(num) {
let root = Math.sqrt(num);
return root === Math.floor(root);
}
const n = A.length;
A.sort((a, b) => a - b);
const graph = {};
for (let x of A) graph[x] = [];
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
if (i !== j && isSquare(A[i] + A[j])) {
graph[A[i]].push(A[j]);
}
}
}
const count = {};
for (let x of A) count[x] = (count[x] || 0) + 1;
function dfs(x, count, length) {
if (length === n) return 1;
let total = 0;
for (let y of graph[x]) {
if (count[y]) {
count[y]--;
total += dfs(y, count, length + 1);
count[y]++;
}
}
return total;
}
let res = 0;
for (let x in count) {
count[x]--;
res += dfs(Number(x), count, 1);
count[x]++;
}
return res;
}
A of integers, your task is to find out how many permutations of A form a "squareful array." An array is squareful if, for every pair of consecutive elements A[i] and A[i+1], the sum A[i] + A[i+1] is a perfect square (that is, the square of some integer). Each permutation must use every element of A exactly once, and duplicate permutations due to duplicate elements should be counted only once.
A and count those where all adjacent sums are perfect squares. However, this brute-force approach is inefficient, especially with duplicate elements, since it explores many redundant cases. To optimize, we need to avoid duplicate permutations and prune impossible paths early. By thinking of the problem as building a path where each step connects to the next number if their sum is a perfect square, we can model the problem as a graph traversal. This leads us to consider depth-first search (DFS) with backtracking, using a counter to avoid reusing elements and to prevent counting duplicate permutations.
A, check if their sum is a perfect square. If so, create an edge between them. This graph tells us which numbers can follow each other in a valid permutation.A. This helps us avoid reusing elements more than their actual occurrence.A's length) found from all possible starting numbers.A = [1, 17, 8].
n elements is O(n!), and for each, checking adjacent pairs is O(n), leading to O(n! * n) time. Space is O(n) for recursion stack.