0996. 平方数组的数目【困难】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 回溯 + 剪枝

1. 📝 题目描述

• leetcode

如果一个数组的任意两个相邻元素之和都是完全平方数，则该数组称为平方数组。

给定一个整数数组 nums，返回所有属于平方数组的 nums 的排列数量。

如果存在某个索引 i 使得 perm1[i] != perm2[i]，则认为两个排列 perm1 和 perm2 不同。

---

示例 1：

输入：nums = [1,17,8]
输出：2

解释：
[1,8,17] 和 [17,8,1] 是有效的排列。

---

示例 2：

输入：nums = [2,2,2]
输出：1

---

提示：

• 1 <= nums.length <= 12
• 0 <= nums[i] <= 10^9

2. 🎯 s.1 - 回溯 + 剪枝

js

/**
 * @param {number[]} nums
 * @return {number}
 */
var numSquarefulPerms = function (nums) {
  const n = nums.length
  nums.sort((a, b) => a - b) // 排序便于去重

  // 判断两数之和是否为完全平方数
  const isSquare = (x, y) => {
    const sum = x + y
    const sqrt = Math.floor(Math.sqrt(sum))
    return sqrt * sqrt === sum
  }

  // 构建图：记录哪些数字可以相邻
  const graph = Array.from({ length: n }, () => [])
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (isSquare(nums[i], nums[j])) {
        graph[i].push(j)
        graph[j].push(i)
      }
    }
  }

  let count = 0
  const used = new Array(n).fill(false)

  const 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 > 0 && !graph[path[path.length - 1]].includes(i)) {
        continue
      }

      // 选择
      used[i] = true
      path.push(i)

      backtrack(path)

      // 撤销选择
      path.pop()
      used[i] = false
    }
  }

  backtrack([])
  return count
}

• 时间复杂度：$O(n!\times n)$，其中 n 是数组长度，最坏情况需要遍历所有排列
• 空间复杂度：$O(n^2)$，图的邻接表和递归栈空间

算法思路：

• 预处理：排序数组便于去重，构建图记录哪些索引对应的数字可以相邻（和为完全平方数）
• 回溯框架：从空路径开始，逐个选择未使用的数字添加到路径中
• 剪枝策略 1：跳过已使用的元素和重复元素（nums[i] === nums[i-1] 且前一个未使用）
• 剪枝策略 2：检查当前元素是否可以与路径最后一个元素相邻，不满足则跳过
• 终止条件：当路径长度等于 n 时，找到一个有效排列，计数加 1