LeetCode-in-Java

996. Number of Squareful Arrays

Hard

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

Solution

import java.util.HashSet;
import java.util.Set;

public 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;
    }
}

This site is open source. Improve this page.