Number of Squareful Arrays: Backtracking with Graph Modeling

LeetCode Number of Squareful Arrays (problem 996) asks you to count the number of permutations of an integer array where every pair of adjacent elements sums to a perfect square. A permutation is called "squareful" if this property holds for all consecutive pairs. Given the array nums, return the number of squareful permutations.

Why this problem matters

This problem sits at the intersection of three core algorithmic ideas: backtracking, graph theory, and number theory. You need to recognize that the adjacency constraint (sum must be a perfect square) transforms the problem from raw permutation enumeration into a graph traversal problem. Once you see that connection, the solution becomes much cleaner. It is a great example of how reframing a combinatorial problem as a graph problem can simplify both the reasoning and the implementation.

The key insight

Think of each element in the array as a node in a graph. Draw an edge between two nodes if their sum is a perfect square. Now the question becomes: how many Hamiltonian paths exist in this graph? A Hamiltonian path visits every node exactly once, which is exactly what a permutation does.

For example, with [1, 17, 8], the graph has edges between 1 and 8 (since 1+8=9=3x3) and between 8 and 17 (since 8+17=25=5x5). There is no edge between 1 and 17 because 1+17=18 is not a perfect square. The Hamiltonian paths are 1 -> 8 -> 17 and 17 -> 8 -> 1, giving an answer of 2.

The backtracking approach tries each unused node as the next step, but only follows edges that exist in the adjacency graph. This prunes the search space dramatically compared to generating all permutations and checking each one.

The solution

from math import isqrt
from collections import Counter

def num_squareful_perms(nums):
    n = len(nums)
    count = Counter(nums)

    def is_square(x):
        s = isqrt(x)
        return s * s == x

    graph = {}
    unique = list(count.keys())
    for i in range(len(unique)):
        graph[unique[i]] = []
        for j in range(len(unique)):
            if is_square(unique[i] + unique[j]):
                graph[unique[i]].append(unique[j])

    result = 0

    def backtrack(val, remaining):
        nonlocal result
        if remaining == 0:
            result += 1
            return
        for neighbor in graph[val]:
            if count[neighbor] > 0:
                count[neighbor] -= 1
                backtrack(neighbor, remaining - 1)
                count[neighbor] += 1

    for val in count:
        count[val] -= 1
        backtrack(val, n - 1)
        count[val] += 1

    return result

The solution builds an adjacency graph where each unique value maps to a list of values it can be adjacent to (their sum is a perfect square). Instead of tracking indices, we use a Counter to handle duplicates naturally. When we decrement and increment the count for each value during backtracking, duplicate values are automatically treated as interchangeable, which prevents counting the same permutation more than once.

The outer loop tries each unique value as the starting element. For each start, the backtracking function explores all valid neighbors that still have remaining count, building the permutation one step at a time.

Visual walkthrough

The walkthrough above uses the example [1, 17, 8]. Notice how starting from node 8 leads to dead ends in both directions, because 8 sits in the middle of the only valid chain. The graph structure makes it clear why only two permutations work: you can traverse the chain left-to-right or right-to-left, but you cannot start from the middle and reach both endpoints.

Complexity analysis

The worst-case time complexity is O(n!) because in the degenerate case every pair of elements could have a perfect square sum, meaning every permutation is valid. The extra factor of n comes from the path length at each recursive call. In practice, the adjacency constraint prunes most branches, so the actual running time is much better than n factorial for typical inputs.

The space complexity is O(n) for the recursion stack and the Counter. The adjacency graph uses O(n^2) space in the worst case for storing edges between all unique pairs, but since n is at most 12 in this problem, the space is negligible.

The building blocks

1. Perfect square check

The helper function is_square(x) uses integer square root to avoid floating-point precision issues. By computing isqrt(x) and squaring the result, you get an exact check. This is a common technique in problems involving perfect squares, and you will see it in many number theory problems. Never use sqrt from the math module and compare with a float, because rounding errors can produce wrong answers for large numbers.

2. Backtracking with duplicate handling

The standard backtracking template picks an element, recurses, then undoes the pick. The twist here is using a Counter to track available elements by value rather than by index. This approach collapses all identical values into a single count, so the backtracking tree never branches into two identical subtrees. If you have three 2s in the array, the counter says "I have three 2s available" rather than distinguishing between the first, second, and third 2.

Edge cases

• All elements identical. If every element is the same value v, then v + v must be a perfect square for any valid permutation. If it is, there is exactly one distinct permutation (they are all the same). If not, the answer is 0.
• Array of length 1. A single element is trivially squareful. The answer is 1.
• No valid pairs. If no two elements sum to a perfect square, the answer is 0 for arrays of length 2 or more.
• Large duplicate counts. With n up to 12 and many duplicates, the Counter-based approach prevents exponential blowup from treating identical elements as distinct.
• Two elements. Check if their sum is a perfect square. If the two values are different, the answer is 2 (two orderings) when the sum is square, 0 otherwise. If they are the same, the answer is 1 when 2 * v is a perfect square.

From understanding to recall

The core insight to internalize is the graph modeling step. When you see a constraint on adjacent pairs in a permutation, think "graph where edges represent valid adjacencies" and then think "count Hamiltonian paths." That mental translation is the hardest part to recall under pressure.

Practice reconstructing the solution in three phases. First, write the is_square helper. Second, build the adjacency graph from unique values. Third, write the backtracking loop with the Counter. Each phase is small and self-contained, which makes the whole solution easier to hold in memory.

The duplicate handling trick (Counter instead of visited set) is worth practicing separately. Try applying it to Permutations II or similar problems where you need distinct permutations of an array with repeated elements. Once the pattern feels natural, you will not need to think about it during an interview.

Related posts

• Permutations II - Generating all distinct permutations of an array with duplicates using sorting and backtracking
• Combination Sum II - Backtracking with pruning to avoid duplicate combinations from a candidate list
• Number of Islands - Graph traversal patterns for exploring connected components in a grid

The Number of Squareful Arrays problem is a beautiful blend of graph modeling and constrained backtracking. Once you see the adjacency graph, the solution writes itself. The Counter-based duplicate handling is the final piece that makes it clean and efficient. Practice the three-phase reconstruction until you can write it from scratch without hesitation.