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. 1 <= A.length <= 12
2. 0 <= A[i] <= 1e9

## Solution1: DFS

Try all permutations with pruning.

Time complexity: O(n!)
Space complexity: O(n)

## Solution 2: DP Hamiltonian Path

dp[s][i] := # of ways to reach state s (binary mask of nodes visited) that ends with node i

dp[s | (1 << j)][j] += dp[s][i] if g[i][j]

Time complexity: O(n^2*2^n)
Space complexity: O(2^n)

## Related Problems

If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website ## Be First to Comment

Mission News Theme by Compete Themes.