Question
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
Difficulty:Hard
Category:
Analyze
Solution 1: DFS
Time complexity: O(n!) Space complexity: O(n)
// Runtime: 4 ms, faster than 100.00% of C++ online submissions for Number of Squareful Arrays.
// Memory Usage: 9 MB, less than 100.00% of C++ online submissions for Number of Squareful Arrays.
class Solution {
public:
int numSquarefulPerms(vector<int>& A) {
std::sort(begin(A), end(A));
vector<int> out;
vector<int> used(A.size(), 0);
int ans = 0;
permuteUniqueDFS(A, used, out, ans);
return ans;
}
private:
void permuteUniqueDFS(vector<int>& nums, vector<int>& used, vector<int>& out, int& ans) {
if (out.size() == nums.size()) {
++ans;
return;
}
for (int i = 0; i < nums.size(); ++i) {
if (used[i]) continue;
// Same number can be only used once at each depth.
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
if (!out.empty() && !squareful(out.back(), nums[i])) continue;
used[i] = 1;
out.emplace_back(nums[i]);
permuteUniqueDFS(nums, used, out, ans);
out.pop_back();
used[i] = 0;
}
}
bool squareful(int x, int y) {
int s = sqrt(x + y);
return s * s == x + y;
}
};
Solution 2: DFS
This solution come from the discuss
Explanation:
- Count numbers ocuurrence.
- For each number
i
, find all possible next numberj
thati + j
is square. - Backtracking using dfs.
Time Complexity
It's O(N^N)
if we have N different numbers and any pair sum is square.
We can easily make case for N = 3 like [51,70,30].
Seems that no hard cases for this problem and int this way it reduces to O(N^2).
// Runtime: 4 ms, faster than 100.00% of C++ online submissions for Number of Squareful Arrays.
// Memory Usage: 8.8 MB, less than 100.00% of C++ online submissions for Number of Squareful
class Solution {
public:
int numSquarefulPerms(vector<int>& A) {
res = 0;
for (int& a : A) count[a]++;
// For each number i, find all possible next number j that i + j is square.
for (auto& i : count) {
for (auto& j : count) {
int x = i.first, y = j.first, s = sqrt(x + y);
if (s * s == x + y) cand[x].insert(y);
}
}
for (auto e : count) dfs(e.first, A.size() - 1);
return res;
}
private:
unordered_map<int, int> count;
unordered_map<int, unordered_set<int>> cand;
int res;
void dfs(int x, int len) {
count[x]--;
if (len == 0) res++;
for (int y : cand[x])
if (count[y] > 0) dfs(y, len - 1);
count[x]++;
}
};
Solution 3: depth
This solution come from: 花花酱 LeetCode 996. Number of Squareful Arrays
class Solution {
public:
int numSquarefulPerms(vector<int>& A) {
const int n = A.size();
// For deduplication.
std::sort(begin(A), end(A));
// g[i][j] == 1 if A[i], A[j] are squareful.
vector<vector<int>> g(n, vector<int>(n, 0));
// dp[s][i] := number of ways to reach state s and ends with node i.
vector<vector<int>> dp(1 << n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j) continue;
int r = sqrt(A[i] + A[j]);
if (r * r == A[i] + A[j]) g[i][j] = 1;
}
}
// For the same numbers, only the first one can be the starting point.
for (int i = 0; i < n; ++i)
if (i == 0 || A[i] != A[i - 1]) dp[(1 << i)][i] = 1;
int ans = 0;
for (int s = 0; s < (1 << n); ++s)
for (int i = 0; i < n; ++i) {
if (!dp[s][i]) continue;
for (int j = 0; j < n; ++j) {
if (!g[i][j]) continue;
if (s & (1 << j)) continue;
// Only the first one can be used as the dest.
if (j > 0 && !(s & (1 << (j - 1))) && A[j - 1] == A[j]) continue;
dp[s | (1 << j)][j] += dp[s][i];
}
}
for (int i = 0; i < n; ++i) ans += dp[(1 << n) - 1][i];
return ans;
}
};