LeetCode 996.正方形数组的数目

和上一道状压的区别在于我们要去重一下~

思路都是和上一篇博客是一样的，感兴趣的同学可以看一下

const int N = 15;
int dp[1<<N][N];
int n;
vector<int>nums1;bool check(int x){int tem  = sqrt(x);if(tem*tem==x)return 1;return 0;
}int dfs(int u,int id){if(u==0)return 1;if(~dp[u][id])return dp[u][id];int res = 0;for(int i=0;i<n;i++){if(((u>>i)&1) && check(nums1[i]+nums1[id]))res = res + dfs(u&~(1<<i),i);}return dp[u][id] = res;
}class Solution {
public:int numSquarefulPerms(vector<int>& nums) {n = nums.size();nums1 = nums;memset(dp,-1,sizeof dp);int ans = 0;int u = (1<<n)-1;for(int i=0;i<n;i++)ans = ans + dfs(u&~(1<<i),i);map<int,int>mp;for(auto &t:nums)++mp[t];for(auto [_,cnt]:mp){while(cnt){ans/=cnt;cnt--;}}return ans;}
};