996. Number of Squareful Arrays
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 <= 12
0 <= nums[i] <= 109
Solutions
Solution: Backtracking + Bitmask
- Time complexity: O(n!)
- Space complexity: O(n)
JavaScript
js
/**
* @param {number[]} nums
* @return {number}
*/
const numSquarefulPerms = function (nums) {
const n = nums.length;
let result = 0;
const findSquarefulPrem = (last, used, length) => {
if (length === n) {
result += 1;
return;
}
for (let index = 0; index < n; index++) {
if ((1 << index) & used) continue;
const num = nums[index];
const isPreviousUsed = (1 << (index - 1)) & used;
if (num === nums[index - 1] && !isPreviousUsed) continue;
const sum = last + num;
if (!Number.isInteger(Math.sqrt(sum))) continue;
findSquarefulPrem(num, (1 << index) | used, length + 1);
}
};
nums.sort((a, b) => a - b);
for (let index = 0; index < n; index++) {
const num = nums[index];
if (num === nums[index - 1]) continue;
findSquarefulPrem(num, 1 << index, 1);
}
return result;
};