LeetCode Q 996 - Number of Squareful Arrays

Given an array A of non-negative integers, the array is squareful if for every pair of adjacent elements, their sum is a perfect square.

Return the number of permutations of A that are squareful. Two permutations A1 and A2 differ if and only if there is some index i such that A1[i] != A2[i].

Example 1: Input: [1,17,8] ; Output: 2
Explanation: [1,8,17] and [17,8,1] are the valid permutations.
Example 2: Input: [2,2,2] ; Output: 1

Note:

1 <= A.length <= 12
0 <= A[i] <= 1e9

similarQ

Solution

Solution 1 : Using Array

Code:

private int res;
    
public int numSquarefulPerms(int[] A) {
  Arrays.sort(A);
  backtrack(A, new ArrayList<>(), new boolean[A.length]);
  return res;
}

private void backtrack(int[] A, List<Intger> temp, int[] visited) {
  if (temp.size() == A.length) {
    res++; return;
  }

  for (int i = 0; i < A.length; i++) {
    if (visited[i]) continue;
    if (i > 0 && A[i] == A[i - 1] && !visited[i - 1]) continue;

    if (temp.size() > 0 && !isSquare(temp.get(temp.size() - 1) + A[i])) continue;

    visited[i] = true;
    temp.add(visited[i]);
    backtrack(A, temp, visited);
    temp.remove(temp.size() - 1);
    visited[i] = false;
  }
}

private boolean isSquare(int x) {
  return (double)Math.sqrt(x) == (int)Math.sqrt(x);
}

Reprint policy