C++のSquareful配列の数

正の整数の配列Aがあるとすると、隣接する要素のすべてのペアについて、それらの合計が完全な正方形である場合、配列は平方であると言えます。二乗であるAの順列の数を見つける必要があります。 2つの順列A1とA2は、A1[i]がA2[i]と同じではないようなインデックスiがある場合にのみ、同じにはなりません。

したがって、入力が[3,30,6]の場合、[3,6,30]、[30,6,3]のような2つの順列があるため、出力は2になります。

これを解決するには、次の手順に従います-

• 関数isSqr（）を定義します。これにはnが必要です。

  • x：=nの平方根

  • （x * x）がn

    と同じ場合にtrueを返します

• 関数solve（）を定義します。これは、配列a、idx、

  を取ります。

  • idxがaのサイズと同じ場合、-

    • （カウントを1つ増やします）

    • 戻る

  • 訪問した1セットを定義する

  • 初期化i：=idxの場合、i

    • （idxが0またはisSqr（a [idx-1] + a [i]））と同じであり、a [i]が訪問されていない場合、-

      • swap（a [idx]、a [i]）

      • 解決（a、idx + 1）

      • swap（a [idx]、a [i]）

      • 訪問先にa[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}

出力

2