996. Number of Squareful Arrays

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] <= 10^9

Solution

class Solution {
    int count;

    public int numSquarefulPerms(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return count;
        }
        backtrack(nums, n, 0);
        return count;
    }

    private void backtrack(int[] nums, int n, int start) {
        if (start == n) {
            count++;
        }
        Set<Integer> set = new HashSet<>();
        for (int i = start; i < n; i++) {
            if (set.contains(nums[i])) {
                continue;
            }
            swap(nums, start, i);
            if (start == 0 || isPerfectSq(nums[start], nums[start - 1])) {
                backtrack(nums, n, start + 1);
            }
            swap(nums, start, i);
            set.add(nums[i]);
        }
    }

    private void swap(int[] array, int a, int b) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

    private boolean isPerfectSq(int a, int b) {
        int x = a + b;
        double sqrt = Math.sqrt(x);
        return sqrt - (int) sqrt == 0;
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).