Number of Squareful Arrays - Solution & Explanation

Problem Overview: You are given an array of integers and must count how many permutations exist such that the sum of every pair of adjacent elements is a perfect square. Arrays may contain duplicates, so permutations that produce the same ordering should only be counted once.

Approach 1: Backtracking with HashSet (O(n!) time, O(n) space)

This approach generates permutations using depth‑first search while enforcing the square condition during construction. First, sort the array so duplicate handling becomes straightforward. During recursion, maintain a visited array and only place a number if it hasn't been used and if the sum with the previously placed element forms a perfect square. A small optimization is precomputing which pairs form perfect squares or checking with int(sqrt(a+b))^2 == a+b. Duplicate permutations are avoided by skipping equal elements that haven't been used in the previous position of the recursion layer. The recursion tree prunes heavily because many pairs will not produce perfect squares, making it much faster than naive permutation generation.

This method directly models the permutation constraint and is often the first correct solution candidates arrive at. It relies on recursion and pruning techniques common in backtracking problems. Space usage stays O(n) for the recursion stack and visited tracking.

Approach 2: Dynamic Programming with Bitmasking (O(n² * 2ⁿ) time, O(n * 2ⁿ) space)

This approach treats the problem as building permutations incrementally using subset DP. Represent which elements are already used with a bitmask of length n. Define dp[mask][i] as the number of valid permutations using elements in mask where the last element is index i. For each state, try extending the permutation with an unused index j. The transition is valid only if nums[i] + nums[j] forms a perfect square.

Before the DP loop, build an adjacency matrix showing which pairs produce square sums. This avoids recomputing square checks during transitions. Duplicate values require careful handling: when selecting an element, skip indices where the previous identical value hasn't been used in the mask. Bitmask DP systematically explores subsets and ensures each state is computed once, which is why the complexity becomes O(n² * 2ⁿ). This technique is common in permutation counting and Hamiltonian‑path style problems using dynamic programming and bitmasking.

Recommended for interviews: Start with the backtracking solution because it mirrors the problem statement: build permutations while enforcing the square constraint. Interviewers often expect pruning logic and duplicate handling. The bitmask DP approach demonstrates stronger algorithmic depth and familiarity with subset DP patterns, which can stand out in senior‑level interviews.