Skip to main content
Talentd

Number of Squareful Arrays - Solution & Explanation

HardArrayHash TableMathDynamic Programming9 min readAsked at: Apple, Google
Practice this problem

Problem Statement

An array is squareful if the sum of every pair of adjacent elements is a perfect square.

Given an integer array nums, return the number of permutations of nums that are squareful.

Two permutations perm1 and perm2 are different if there is some index i such that perm1[i] != perm2[i].

 

Example 1:

Input: nums = [1,17,8]
Output: 2
Explanation: [1,8,17] and [17,8,1] are the valid permutations.

Example 2:

Input: nums = [2,2,2]
Output: 1

 

Constraints:

  • 1 <= nums.length <= 12
  • 0 <= nums[i] <= 109

Approach Overview

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(n2 * 2n) time, O(n * 2n) 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(n2 * 2n). 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.

Approach 1: Approach 1: Backtracking with HashSet

This approach uses backtracking to generate all permutations of the array. For each permutation, it checks if the sum of every pair of adjacent elements is a perfect square. To optimize, a HashSet is used to avoid duplicates.

The solution generates all unique permutations using itertools.permutations and checks each for squarefulness. It counts those that pass the check. A helper function is_squareful verifies if adjacent pairs are perfect squares.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n!), where n is the length of nums, due to generating all permutations.
Space Complexity: O(n!), for storing permutations in a set.

Try this approach in the editor →

Approach 2: Approach 2: Dynamic Programming with Bitmasking

This approach uses dynamic programming with bitmasking to generate permutations. A bitmask represents used elements. Recursion with memoization checks if a permutation is squareful.

This solution uses a recursive function with bitmasking to represent which elements have been used. The helper function dfs is called repeatedly to explore all combinations. Memoization is implemented to reduce repeated computations.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n * 2^n), due to subsets of elements explored.
Space Complexity: O(n * 2^n), due to memoization of states.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Backtracking with HashSet

Time Complexity: O(n!), where n is the length of nums, due to generating all permutations.
Space Complexity: O(n!), for storing permutations in a set.

Approach 2: Dynamic Programming with Bitmasking

Time Complexity: O(n * 2^n), due to subsets of elements explored.
Space Complexity: O(n * 2^n), due to memoization of states.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking with HashSetO(n!)O(n)Good for understanding the constraint directly and implementing pruning with recursion
Dynamic Programming with BitmaskO(n² · 2ⁿ)O(n · 2ⁿ)Preferred when counting permutations with state reuse and subset DP optimization

Video Solution

NUMBER OF SQUAREFUL ARRAYS | LEETCODE 996 | PYTHON BACKTRACKING SOLUTION • Cracking FAANG • 2,804 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Number of Squareful Arrays easy or hard?
LeetCode classifies Number of Squareful Arrays as a Hard problem. The difficulty comes from combining permutation generation, duplicate handling, and perfect-square constraints, often requiring either careful backtracking pruning or bitmask dynamic programming.
Number of Squareful Arrays Python/Java solution
Python and Java solutions typically implement DFS backtracking with a visited array and sorted input to skip duplicates. The DP variant uses a 2D array indexed by bitmask and last position, iterating through valid square-sum neighbors to update states.
How to solve Number of Squareful Arrays in O(n^2 * 2^n)?
Use subset dynamic programming with bitmasks. Define dp[mask][i] as the number of valid permutations using elements in mask and ending at index i. Precompute which pairs of values sum to perfect squares, then transition by adding unused indices whose sums satisfy the square condition.
What is the best approach for Number of Squareful Arrays?
The most robust solution uses dynamic programming with bitmasking. It models the problem as building permutations of indices and stores intermediate results in dp[mask][i]. This reduces repeated work and runs in O(n^2 * 2^n) time, which is efficient for the constraint n ≤ 12. Backtracking with pruning is also widely accepted in interviews.
Is Number of Squareful Arrays asked at Google/Amazon/Meta?
Permutation counting and subset dynamic programming problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving bitmask DP, Hamiltonian paths, or constraint-based permutations are common patterns tested in senior algorithm rounds.
What data structure is used in Number of Squareful Arrays?
Typical implementations use arrays, hash sets for duplicate handling, recursion stacks for backtracking, and bitmasks for subset representation. In the optimized solution, a 2D DP table dp[mask][i] stores counts of permutations ending at index i.
What is the time complexity of Number of Squareful Arrays?
Backtracking solutions can take up to O(n!) time because they explore permutations, although pruning removes many invalid branches. The optimized approach uses bitmask dynamic programming with O(n^2 * 2^n) time and O(n * 2^n) space by reusing results for previously computed subsets.

Ready to solve this problem?

Practice Number of Squareful Arrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Permutations II