Leetcode 996. 正方形数组的数目(回溯算法+全排列问题)

2020-06-13

字数统计: 397字 | 阅读时长≈ 1分

问题描述

给定一个非负整数数组 A，如果该数组每对相邻元素之和是一个完全平方数，则称这一数组为正方形数组。

返回 A 的正方形排列的数目。两个排列 A1 和 A2 不同的充要条件是存在某个索引 i，使得 A1[i] != A2[i]。

Example

示例1

输入：[1,17,8]

输出：2

解释：

[1,8,17] 和 [17,8,1] 都是有效的排列。

示例2

输入：[2,2,2]

输出：1

Note

1 <= A.length <= 12
0 <= A[i] <= 1e9

题目链接:996. 正方形数组的数目 (难度:困难)

思路

这个问题可以看成是一个约束条件的全排列问题，其中约束条件为：对于特定的排列 A，必须满足 A[i] + A[i + 1] 为完全平方数。

可以采用 DFS 算法枚举所有的全排列，对于若当前排列不满足约束条件则回溯

代码

class Solution {
public:
    vector<int> res;
    bool visited[12] = {false};
    void dfs(vector<int>& nums, int idx, int len, int& ans){
        if(idx == len){
            ++ans;
            return;
        }
        int sample = -1;
        for(int i = 0;i < len;++i){
            if(visited[i] || sample == nums[i]){
                continue;
            }
            if(!res.empty()){
                int sum = nums[i] + res.back();
                int factor = sqrt(sum);
                if(factor * factor != sum){
                    continue;
                }
            }
            res.push_back(nums[i]);
            visited[i] = true;
            sample = nums[i];
            dfs(nums,idx + 1, len, ans);
            visited[i] = false;
            res.pop_back();
        }
    }
    int numSquarefulPerms(vector<int>& A) {
        if(A.empty()) return 0;
        int len = A.size();
        if(len == 1)  return 1;
        sort(A.begin(),A.end());
        int ans = 0;
        dfs(A, 0, len, ans);
        return ans;
    }
};

**执行结果 : ** 0 ms, 7.9 MB

本文作者： Phoenix
本文链接： https://phoenix500526.github.io/2020/06/13/Leetcode-996-正方形数组的数目-回溯算法-全排列问题/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！