996. Number of Squareful Arrays

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int ans ;
    vector<bool> visited;
    void dfs(vector<int> & nums, vector<int> & path){
        if(path.size() == nums.size()){
            ans++;
        }
        
        for(int i=0;i<nums.size();++i){
            if (i > 0 && nums[i] == nums[i - 1] && visited[i - 1] == false) continue;
            if(visited[i] ) continue;
            
            if(!path.empty()){
                double root = sqrt(nums[i]+path.back());
                if(root- floor(root)!= 0 ) continue;
            }
            
            visited[i] = true;
            path.push_back(nums[i]);
            dfs(nums, path);
            path.pop_back();
            visited[i] = false;
        }
    }
    int numSquarefulPerms(vector<int>& nums) {
        ans = 0;
        sort(nums.begin(), nums.end());
        vector<int> path;
        visited = vector<bool>(nums.size(), false);
        dfs(nums, path);
        return ans;
        
    }
};