Number of Squareful Arrays

hard backtracking permutations perfect square

Problem

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 are different if there is some index i where they differ in value.

Inputnums = [1, 17, 8]

Output2

[1, 8, 17] (1+8=9, 8+17=25) and [17, 8, 1] are both squareful, so the count is 2.

nums (comma-separated)

def numSquarefulPerms(nums):
    nums.sort()
    n = len(nums)
    used = [False] * n
    count = 0

    def is_square(x):
        r = int(x ** 0.5)
        return r * r == x

    def backtrack(path):
        nonlocal count
        if len(path) == n:
            count += 1
            return
        for i in range(n):
            if used[i]:
                continue
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            if path and not is_square(path[-1] + nums[i]):
                continue
            used[i] = True
            backtrack(path + [nums[i]])
            used[i] = False

    backtrack([])
    return count

function numSquarefulPerms(nums) {
  nums.sort((a, b) => a - b);
  const n = nums.length;
  const used = new Array(n).fill(false);
  let count = 0;

  const isSquare = (x) => {
    const r = Math.round(Math.sqrt(x));
    return r * r === x;
  };

  function backtrack(path) {
    if (path.length === n) { count++; return; }
    for (let i = 0; i < n; i++) {
      if (used[i]) continue;
      if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;
      if (path.length && !isSquare(path[path.length - 1] + nums[i])) continue;
      used[i] = true;
      path.push(nums[i]);
      backtrack(path);
      path.pop();
      used[i] = false;
    }
  }

  backtrack([]);
  return count;
}

class Solution {
    int n, count = 0;
    int[] nums;
    boolean[] used;

    public int numSquarefulPerms(int[] nums) {
        Arrays.sort(nums);
        this.nums = nums;
        this.n = nums.length;
        this.used = new boolean[n];
        backtrack(new ArrayList<>());
        return count;
    }

    boolean isSquare(int x) {
        int r = (int) Math.sqrt(x);
        return r * r == x;
    }

    void backtrack(List<Integer> path) {
        if (path.size() == n) { count++; return; }
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            if (!path.isEmpty() && !isSquare(path.get(path.size() - 1) + nums[i])) continue;
            used[i] = true;
            path.add(nums[i]);
            backtrack(path);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

class Solution {
public:
    int n, count = 0;
    vector<int> nums;
    vector<bool> used;

    bool isSquare(int x) {
        int r = (int) sqrt((double) x);
        return r * r == x;
    }

    void backtrack(vector<int>& path) {
        if ((int)path.size() == n) { count++; return; }
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            if (!path.empty() && !isSquare(path.back() + nums[i])) continue;
            used[i] = true;
            path.push_back(nums[i]);
            backtrack(path);
            path.pop_back();
            used[i] = false;
        }
    }

    int numSquarefulPerms(vector<int>& input) {
        sort(input.begin(), input.end());
        nums = input;
        n = nums.size();
        used.assign(n, false);
        vector<int> path;
        backtrack(path);
        return count;
    }
};

Explanation

We want to count permutations where every neighboring pair sums to a perfect square. We build permutations one element at a time with backtracking, and only extend a path when the new neighbor pair is a perfect square.

First we sort nums so equal values sit next to each other. The used array tracks which positions are already in the current path. The backtrack(path) function adds an unused number, recurses, then removes it.

Two checks keep things correct. The square check is_square(path[-1] + nums[i]) prunes any placement whose adjacent sum is not a perfect square. The duplicate check i > 0 and nums[i] == nums[i-1] and not used[i-1] skips an equal value whose twin hasn't been used yet, so we don't count the same permutation multiple times.

Example: nums = [1, 17, 8]. The path [1, 8, 17] works because 1+8=9 and 8+17=25 are both squares; its reverse [17, 8, 1] also works. So the count is 2.

Every time a path reaches full length it is a valid squareful permutation, and we increment count.

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