C++의 정사각형 배열 수

<시간/>

양의 정수로 구성된 배열 A가 있다고 가정하고 인접한 요소의 모든 쌍에 대해 합이 완전 제곱이면 배열은 제곱이라고 말할 수 있습니다. 제곱인 A의 순열 수를 찾아야 합니다. 두 순열 A1과 A2는 A1[i]가 A2[i]와 같지 않은 인덱스 i가 있는 경우에만 동일하지 않습니다.

따라서 입력이 [3,30,6]과 같으면 [3,6,30], [30,6,3]과 같은 두 개의 순열이 있으므로 출력은 2가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

isSqr() 함수를 정의하면 n이 필요합니다.
- x :=n의 제곱근
- (x * x)가 n
  과 같을 때 true를 반환합니다.
solve() 함수를 정의하면 배열 a, idx,
가 사용됩니다.
- idx가 크기와 같으면 -
  - (1씩 증가)
  - 반환
- 방문한 한 세트 정의
- initialize i :=idx의 경우 i
  - (idx가 0 또는 isSqr(a[idx - 1] + a[i]))이고 a[i]가 방문하지 않은 경우 -
    - 스왑(a[idx], a[i])
    - 해결(a, idx + 1)
    - 스왑(a[idx], a[i])
    - 방문
      에 [i] 삽입
기본 방법에서 다음을 수행하십시오 -
개수 :=0
풀다(a, 0)
반환 횟수

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   int count;
   bool isSqr(lli n){
      lli x = sqrt(n);
      return x * x == n;
   }
   void solve(vector<int>& a, int idx){
      if (idx == a.size()) {
         count++;
         return;
      }
      set<int> visited;
      for (int i = idx; i < a.size(); i++) {
         if ((idx == 0 || isSqr(a[idx - 1] + a[i])) &&
         !visited.count(a[i])) {
            swap(a[idx], a[i]);
            solve(a, idx + 1);
            swap(a[idx], a[i]);
            visited.insert(a[i]);
         }
      }
   }
   int numSquarefulPerms(vector<int>& a){
      count = 0;
      solve(a, 0);
      return count;
   }
};
main(){
   Solution ob;
   vector<int> v = {3,30,6};
   cout << (ob.numSquarefulPerms(v));
}

입력

{3,30,6}