Description
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 <= 120 <= nums[i] <= 109
Solutions
Solution 1
PythonJavaC++Go
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(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
func numSquarefulPerms(nums []int) (ans int) {
n := len(nums)
f := make([][]int, 1<<n)
for i := range f {
f[i] = make([]int, n)
}
for j := range nums {
f[1<<j][j] = 1
}
for i := 0; i < 1<<n; i++ {
for j := 0; j < n; j++ {
if i>>j&1 == 1 {
for k := 0; k < n; k++ {
if i>>k&1 == 1 && k != j {
s := nums[j] + nums[k]
t := int(math.Sqrt(float64(s)))
if t*t == s {
f[i][j] += f[i^(1<<j)][k]
}
}
}
}
}
}
for j := 0; j < n; j++ {
ans += f[(1<<n)-1][j]
}
g := [13]int{1}
for i := 1; i < 13; i++ {
g[i] = g[i-1] * i
}
cnt := map[int]int{}
for _, x := range nums {
cnt[x]++
}
for _, v := range cnt {
ans /= g[v]
}
return
}(code-box)
