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
-
Method 1: search O(N!) AC 3ms
- Pruning is super important, I cannot AC without pruning.
- need to check if the last two variables are squareful.
class Solution { private int res = 0; public int numSquarefulPerms(int[] A) { if(A.length == 1) return 0; Arrays.sort(A); dfs(A, new ArrayList<Integer>(), 0); return res; } private void dfs(int[] A, List<Integer> temp, int visited){ if(temp.size() == A.length){ boolean flag = true; for(int i = 1; i < A.length; i++){ flag &= square(temp.get(i - 1) + temp.get(i)); } if(flag) res++; }else if(temp.size() <= 1 || square(temp.get(temp.size() - 1) + temp.get(temp.size() - 2))){ for(int i = 0; i < A.length; i++){ if((visited & (1 << i)) > 0) continue; if(i > 0 && A[i] == A[i - 1] && (visited & (1 << (i - 1))) == 0) continue; temp.add(A[i]); dfs(A, temp, visited | (1 << i)); temp.remove(temp.size() - 1); } } } private boolean square(int sum){ return (int)Math.sqrt(sum) * (int)Math.sqrt(sum) == sum; } }
-
Method 2: DP AC 99.23%
- dp[i][state]: i means current index and state is a bit map show what are the next index to visit(which are set to 1).
- dp[i][state] = dp[next][next bit is set to zero state] for all non-visited indice.
- Result: sum of all index as head, all other index are not visited state.
class Solution { private int res = 0; public int numSquarefulPerms(int[] A) { if(A.length == 1) return 0; Arrays.sort(A); dfs(A, new ArrayList<Integer>(), 0); return res; } private void dfs(int[] A, List<Integer> temp, int visited){ if(temp.size() == A.length){ boolean flag = true; for(int i = 1; i < A.length; i++){ flag &= square(temp.get(i - 1) + temp.get(i)); } if(flag) res++; }else if(temp.size() <= 1 || square(temp.get(temp.size() - 1) + temp.get(temp.size() - 2))){ for(int i = 0; i < A.length; i++){ if((visited & (1 << i)) > 0) continue; if(i > 0 && A[i] == A[i - 1] && (visited & (1 << (i - 1))) == 0) continue; temp.add(A[i]); dfs(A, temp, visited | (1 << i)); temp.remove(temp.size() - 1); } } } private boolean square(int sum){ return (int)Math.sqrt(sum) * (int)Math.sqrt(sum) == sum; } }
-
Method 1: dfs
class Solution { private int res; public int numSquarefulPerms(int[] A) { if(A.length == 1) return 0; Arrays.sort(A); dfs(A, new ArrayList<Integer>(), new boolean[A.length]); return this.res; } private void dfs(int[] A, List<Integer> temp, boolean[] visited){ if(temp.size() == A.length){ if(square(temp.get(temp.size() - 1) + temp.get(temp.size() - 2))) this.res++; }else if(temp.size() <= 1 || square(temp.get(temp.size() - 1) + temp.get(temp.size() - 2))){ for(int i = 0; i < A.length; i++){ if(visited[i]) continue; if(i > 0 && A[i] == A[i - 1] && !visited[i - 1]) continue; temp.add(A[i]); visited[i] = true; dfs(A, temp, visited); visited[i] = false; temp.remove(temp.size() - 1); } } } private boolean square(int x){ return x == (int)Math.sqrt(x) * (int)Math.sqrt(x); } }
-
Method 2: DP
class Solution { private int[][] dp; private int len; public int numSquarefulPerms(int[] A) { this.len = A.length; dp = new int[len][(1 << len)]; int res = 0; int fullState = (1 << len) - 1; Arrays.sort(A); for(int i = 0; i < len; i++){ if(i > 0 && A[i] == A[i - 1]) continue; res += dfs(A, i, fullState ^ (1 << i)); } return res; } private int dfs(int[] A, int cur, int state){ if(dp[cur][state] > 0) return dp[cur][state]; if(state == 0) return 1; int pre = -1; int index = 0; int copy = state; while(copy != 0){ if(((copy & 1) == 1 && square(A[cur] + A[index]))){ if(pre == A[index]){ index++; copy >>= 1; continue; } pre = A[index]; dp[cur][state] += dfs(A, index, state ^ (1 << index)); } index++; copy >>= 1; } return dp[cur][state]; } private boolean square(int j){ return j == (int)Math.sqrt(j) * (int)Math.sqrt(j); } }
- Method 1: dp
class Solution { private: bool square(int x){ int r = sqrt(x); return x == r * r; } vector<vector<int>> dp_; //dp[cur][state] int dfs(vector<int>& A, int cur, int to_visit){ if(dp_[cur][to_visit]) return dp_[cur][to_visit]; else if(!to_visit) return 1; int copy = to_visit; int pre = -1, index = 0; while(copy){ if((copy & 1) && square(A[cur] + A[index])){ if(pre == A[index]){ index ++; copy >>= 1; continue; } pre = A[index]; dp_[cur][to_visit] += dfs(A, index, to_visit ^ (1 << index)); } index++; copy >>= 1; } return dp_[cur][to_visit]; } public: int numSquarefulPerms(vector<int>& A) { const int n = A.size(); dp_ = vector<vector<int>>(n, vector<int>(1 << n, 0)); sort(A.begin(), A.end()); int res = 0; int fullstate = (1 << n) - 1; for(int i = 0; i < n; ++i){ if(i > 0 && A[i] == A[i - 1]) continue; res += dfs(A, i, fullstate ^ (1 << i)); } return res; } };