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
Solution:
class Solution {
int res = 0;
Set<String> v = new HashSet();
public int numSquarefulPerms(int[] A) {
Set<Integer> set = new HashSet();
Arrays.sort(A);
int n = A.length, max = A[n - 1];
for (int i = 0; i * i <= 2 * max; i ++) {
set.add(i * i);
}
bt(A, 0, set);
return res;
}
private void bt(int[] A, int start, Set<Integer> set) {
if (start == A.length) {
if (v.add(Arrays.toString(A))) {
res ++;
}
return;
}
for (int i = start; i < A.length; i ++) {
if (i > start && A[i] == A[i - 1]) {
continue;
}
if (start == 0 || set.contains(A[i] + A[start - 1])) {
swap(A, i, start);
bt(A, start + 1, set);
swap(A, i, start);
}
}
}
private void swap(int[] A, int x, int y) {
int temp = A[x];
A[x] = A[y];
A[y] = temp;
}
}