文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給定一個非負整數數組 A，如果該數組每對相鄰元素之和是一個完全平方數，則稱這一數組為正方形數組。

返回 A 的正方形排列的數目。兩個排列 A1 和 A2 不同的充要條件是存在某個索引 i，使得 A1[i] != A2[i]。

示例 1： 輸入：[1,17,8] 輸出：2 解釋： [1,8,17] 和 [17,8,1] 都是有效的排列。示例 2： 輸入：[2,2,2] 輸出：1提示： 1 <= A.length <= 12 0 <= A[i] <= 1e9

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/number-of-squareful-arrays
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

類似題目：
LeetCode 47. 全排列 II（回溯+搜索剪枝）
LeetCode 46. 全排列（回溯）

class Solution {int ans = 0; public:int numSquarefulPerms(vector<int>& A) {vector<bool> vis(A.size(), false);sort(A.begin(), A.end());dfs(A, 0, -1, vis);return ans;}void dfs(vector<int>& A, int count, int prev, vector<bool>& vis) {if(count == A.size()){ans++;return;}for(int i = 0; i < A.size(); ++i){if(i > 0 && !vis[i-1] && A[i-1]==A[i])continue;// 剪枝if(!vis[i] && (prev == -1 || ok(prev, A[i]))){vis[i] = true;dfs(A, count+1, A[i], vis);vis[i] = false;}}}bool ok(int a, int b){int num = sqrt(a+b);return num*num == a+b;} };

4 ms 7.8 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 996. 正方形数组的数目（回溯+剪枝）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。