Hard

题目描述

如果数组中每对相邻元素的和都是一个完全平方数，那么这个数组就是平方数组。

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

如果两个排列 perm1 和 perm2 在某个索引 i 处有 perm1[i] != perm2[i]，则它们是不同的。

示例 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

解题思路

这道题要求找到所有满足相邻元素和为完全平方数的排列数量。可以使用两种主要方法：

方法一：回溯法（推荐） 使用回溯搜索所有可能的排列。关键优化包括：

  1. 预处理：构建邻接图，记录哪些数字对的和是完全平方数
  2. 去重：对相同数字进行去重处理，避免重复计算
  3. 剪枝：在构建排列过程中，只选择与当前数字相邻且满足条件的数字

方法二：动态规划 + 状态压缩 使用位掩码表示已使用的数字状态，dp[mask][i] 表示使用状态为 mask 且以数字 i 结尾的方案数。

回溯法更直观易懂，且在数组长度较小时性能较好。实现时需要注意处理重复数字的情况，可以先排序然后在递归中跳过重复元素。

判断完全平方数可以通过计算平方根并验证其整数性来实现。

代码实现

class Solution {
public:
    int numSquarefulPerms(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        
        // 构建邻接图
        vector<vector<bool>> graph(n, vector<bool>(n, false));
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                long long sum = (long long)nums[i] + nums[j];
                long long root = sqrt(sum);
                if (root * root == sum) {
                    graph[i][j] = graph[j][i] = true;
                }
            }
        }
        
        int result = 0;
        vector<bool> used(n, false);
        
        function<void(int, int)> backtrack = [&](int pos, int last) {
            if (pos == n) {
                result++;
                return;
            }
            
            for (int i = 0; i < n; i++) {
                if (used[i]) continue;
                if (pos > 0 && !graph[last][i]) continue;
                if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
                
                used[i] = true;
                backtrack(pos + 1, i);
                used[i] = false;
            }
        };
        
        backtrack(0, -1);
        return result;
    }
};

class Solution:
    def numSquarefulPerms(self, nums: List[int]) -> int:
        import math
        
        n = len(nums)
        nums.sort()
        
        # 构建邻接图
        graph = [[False] * n for _ in range(n)]
        for i in range(n):
            for j in range(i + 1, n):
                sum_val = nums[i] + nums[j]
                root = int(math.sqrt(sum_val))
                if root * root == sum_val:
                    graph[i][j] = graph[j][i] = True
        
        result = 0
        used = [False] * n
        
        def backtrack(pos, last):
            nonlocal result
            if pos == n:
                result += 1
                return
            
            for i in range(n):
                if used[i]:
                    continue
                if pos > 0 and not graph[last][i]:
                    continue
                if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
                    continue
                
                used[i] = True
                backtrack(pos + 1, i)
                used[i] = False
        
        backtrack(0, -1)
        return result

public class Solution {
    public int NumSquarefulPerms(int[] nums) {
        int n = nums.Length;
        Array.Sort(nums);
        
        // 构建邻接图
        bool[,] graph = new bool[n, n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                long sum = (long)nums[i] + nums[j];
                long root = (long)Math.Sqrt(sum);
                if (root * root == sum) {
                    graph[i, j] = graph[j, i] = true;
                }
            }
        }
        
        int result = 0;
        bool[] used = new bool[n];
        
        void Backtrack(int pos, int last) {
            if (pos == n) {
                result++;
                return;
            }
            
            for (int i = 0; i < n; i++) {
                if (used[i]) continue;
                if (pos > 0 && !graph[last, i]) continue;
                if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
                
                used[i] = true;
                Backtrack(pos + 1, i);
                used[i] = false;
            }
        }
        
        Backtrack(0, -1);
        return result;
    }
}

var numSquarefulPerms = function(nums) {
    const n = nums.length;
    const count = {};
    
    // Count frequency of each number
    for (let num of nums) {
        count[num] = (count[num] || 0) + 1;
    }
    
    const unique = Object.keys(count).map(Number);
    const m = unique.length;
    
    // Build adjacency graph
    const graph = Array(m).fill().map(() => []);
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < m; j++) {
            const sum = unique[i] + unique[j];
            const sqrt = Math.sqrt(sum);
            if (sqrt === Math.floor(sqrt)) {
                graph[i].push(j);
            }
        }
    }
    
    let result = 0;
    
    function dfs(path, remaining) {
        if (path.length === n) {
            result++;
            return;
        }
        
        for (let i = 0; i < m; i++) {
            if (remaining[unique[i]] === 0) continue;
            
            if (path.length === 0 || graph[path[path.length - 1]].includes(i)) {
                remaining[unique[i]]--;
                path.push(i);
                dfs(path, remaining);
                path.pop();
                remaining[unique[i]]++;
            }
        }
    }
    
    dfs([], {...count});
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n! × n) - 最坏情况下需要遍历所有排列，每次检查相邻关系
空间复杂度O(n²) - 邻接图存储空间和递归栈空间

相关题目