Acwing the number of square arrays of one question per day

acwing The number of square arrays

Topic ideas

• After the direct arrangement, the inspection will TLE, Therefore, whether the two critical values meet the requirements is directly detected in the sorting process , If you are not satisfied with direct pruning , Greatly reduce the time complexity （ Because few meet the requirements ）
• secondly , Double check the arrangement , The simple way is to store each number in the form of a hash table , Iterate every number with iterators , After use, reduce the number of times . It's used here Y The weight checking method taught by the general manager , It's a little difficult for me , From understanding to writing code independently 1 Hours ,hh

y Introduction to the total duplicate checking method , There is no guarantee that you can make it clear , As your own notes

When we sort the array , The repeated numbers come together , Treat the repeated number set as an interval . If you want to ensure that each arrangement is not repeated, as long as you can ensure that the number taken at this position is only taken once in this interval .
y The general method is to ensure that the number obtained each time is taken in this interval for the first time , Because the arrangement value of each number is checked from the front to the back of the array , For the following picture

Because it is checked from front to back , In the first arrangement, the first number must be red 2, The second one must be blue 2, The third time must be yellow 2, Trace back after this arrangement , the second 2 To the yellow 2 Location , At this time, I found the blue one in front 2 No place to use , It shows that this number is not the first time to use , End directly , Go back to the first 2, first ·2 To traverse to the blue .2, At this time, I found the front 2 There is no place to take , It's not the first time to take this number , End directly

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
int cnt = 0;
int n;
int w[15];
bool used[15];

bool check(int sum){
    // Check whether the sum of the two numbers is square 
    int x = sqrt(sum);
    return x*x == sum;
}

void permutation(int t,int last){
    
    if(t == n){
    
        cnt++;// It shows that it is a square array 
        return;
    }
    
    for(int i=0; i< n; i++){
    
        if(used[i])continue;
        if(i && !used[i-1] && w[i] == w[i-1])continue;// Check whether it is the first time to use the number of this interval 
        if(t && !check(w[i] + last))continue;// If you take the number of the first position , There is no need to check whether the sum of the previous number and this number is a square number 
        used[i] = true;
        permutation(t+1, w[i]);
        used[i] = false;
    }
    
}

int main(){
    
    cin>>n;
    for(int i=0; i<n; i++)cin>>w[i];
    sort(w,w+n);
    permutation(0,0);
    cout<<cnt<<endl;
}