590，回溯算法解正方形数组的数目

Original 博哥数据结构和算法 2022-05-10

问题描述

来源：LeetCode第996题

难度：困难

给定一个非负整数数组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

回溯算法解决

这题是让打乱数组的顺序，打乱之后的数组如果所有的前后两个数字之和是一个完全平方数，那么这个打乱的数组就是正方形数组，这里让求的是正方形数组是个数。

这里我们可以使用回溯算法来解决，我之前专门讲过450，什么叫回溯算法，一看就会，一写就废，回溯算法我们可以把它看做是一棵N叉树，也就是说每个节点最多有N个子节点，然后使用DFS进行遍历。对于这道题我们以示例1为例来看个视频

看懂了这个，这题就非常简单了，之前在讲450题回溯算法的时候，总结了一个模板

private void backtrack("原始参数") {
    //终止条件(递归必须要有终止条件)
    if ("终止条件") {
        //一些逻辑操作（可有可无，视情况而定）
        return;
    }

    for (int i = "for循环开始的参数"; i < "for循环结束的参数"; i++) {
        //一些逻辑操作（可有可无，视情况而定）

        做出选择

        //递归
        backtrack("新的参数");
        //一些逻辑操作（可有可无，视情况而定）

        撤销选择
    }
}

这道题完全可以使用这个模板，每次从数组中选择元素的时候，只能选择未使用的，使用过的则直接跳过，模板的终止条件就是所有元素都访问完了。我们来看下完整代码

//统计正方形数组的个数
int count = 0;

public int numSquarefulPerms(int[] nums) {
    //先对数组进行排序，目的是过滤掉重复的
    Arrays.sort(nums);
    backtrack(nums, new boolean[nums.length], 0, -1);
    return count;
}

/**
 * @param nums
 * @param visited 标记某个数字是否被使用过
 * @param index   当前数字的下标
 * @param preNum  打乱数组的前一个数字
 */
private void backtrack(int[] nums, boolean[] visited, int index, int preNum) {
    //如果数字都访问完了，说明这个打乱的数组是一个正方形数组
    if (index == nums.length) {
        count++;
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        //如果当前数字被访问过，直接跳过
        if (visited[i])
            continue;
        //如果当前数字和前一个数字不能构成完全平方数，直接跳过
        if (preNum > 0 && !isSquare(preNum + nums[i]))
            continue;
        //这里是为了过滤掉重复的，比如数组[2,2,7,9]，我们选择了
        //[2,7(第一个2)]和[2,7(第二个2)]，剩下的数字都是一样的，
        //所以他们的组合也是一样的，会出现重复，我们需要过滤掉
        if ((i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]))
            continue;
        //选择当前数字，标记为已经被使用过
        visited[i] = true;
        //递归，进行到下一层
        backtrack(nums, visited, index + 1, nums[i]);
        //回到上一层，撤销选择
        visited[i] = false;
    }
}

//判断数字num是否是完全平方数
private boolean isSquare(int num) {
    int sqr = (int) Math.sqrt(num);
    return sqr * sqr == num;
}