Number of squareful arrays

Array Hash Table Math Dynamic Programming Backtracking Bit Manipulation Bitmask

51.2% acceptance

Feb 25, 2026

1037

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].

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn num_squareful_perms(mut nums: Vec<i32>) -> i32 {
    fn is_sq(a: i32, b: i32) -> bool {
      let s = ((a+b) as f64).sqrt() as i64;
      s * s == (a + b) as i64
    }
    fn dfs(nums: &mut Vec<i32>, used: &mut Vec<bool>, path: &mut Vec<i32>, count: &mut i32) {
      if path.len() == nums.len() { *count += 1; return; }
      let mut prev = -1i32;
      for i in 0..nums.len() {
        if used[i] { continue; }
        if nums[i] == prev { continue; }
        if let Some(&last) = path.last() {
          if !is_sq(last, nums[i]) { continue; }
        }
        prev = nums[i];
        used[i] = true; path.push(nums[i]);
        dfs(nums, used, path, count);
        used[i] = false; path.pop();
      }
    }
    nums.sort();
    let n = nums.len();
    let mut used = vec![false; n];
    let mut count = 0;
    dfs(&mut nums, &mut used, &mut Vec::new(), &mut count);
    count
  }
}