正方形数组的数目-526互联

给定一个非负整数数组 A，如果该数组每对相邻元素之和是一个完全平方数，则称这一数组为正方形数组。
返回 A 的正方形排列的数目。两个排列 A1 和 A2 不同的充要条件是存在某个索引 i，使得 A1[i] != A2[i]。

1. 回溯法

class Solution {
public:
    int cnt = 0;//记录结果
    bool isSquare(int x){
        return x == (int)sqrt(x) * (int)sqrt(x);
    }

    int numSquarefulPerms(vector<int>& nums) {
        sort(nums.begin(), nums.end());//排序用于防止同一位置重复枚举
        vector<bool> isVisited(nums.size());
        vector<int> temp(nums.size());

        function<void(int)> f = [&](int index)->void{ //枚举不同的全排列
            if(index == nums.size()){//边界条件，计数加一
                cnt++; 
                return;
            }
            for(int i = 0; i < nums.size(); i++){//从所有数中进行枚举
                if(isVisited[i]) continue; //剪枝
                if(i > 0 && nums[i-1] == nums[i] && !isVisited[i-1]) continue; //关键语句，去重，前面的相同数必然在该位置枚举过
                if(index > 0 && !isSquare(temp[index-1] + nums[i])) continue; //剪枝
                temp[index] = nums[i];//做选择
                isVisited[i] = true;
                f(index+1);
                temp[index] = 0;//撤回
                isVisited[i] = false;
            }
        };
        f(0);
        return cnt;
    }
};

正方形