Задача: 996. Number of Squareful Arrays
Сложность: hard

Массив является квадратным, если сумма каждой пары соседних элементов является совершенным квадратом. Если задан целочисленный массив nums, верните количество перестановок nums, которые являются квадратными. Две перестановки perm1 и perm2 различны, если существует некоторый индекс i такой, что perm1[i] != perm2[i].

Пример:

Input: nums = [1,17,8]
Output: 2

👨‍💻 Алгоритм:

1⃣Генерация перестановок:
Сгенерируйте все возможные перестановки массива nums.
Для каждой перестановки проверьте, является ли она квадратной.

2⃣Проверка квадратности:
Для каждой перестановки проверьте, является ли сумма каждой пары соседних элементов совершенным квадратом.
Для этого используйте функцию для проверки, является ли число совершенным квадратом.

3⃣Подсчет квадратных перестановок:
Подсчитайте количество перестановок, которые являются квадратными, и верните это значение.

😎 Решение:

class Solution {
    function numSquarefulPerms($nums) {
        sort($nums);
        $used = array_fill(0, count($nums), false);
        $result = [];
        $path = [];
        $this->backtrack($nums, $used, $path, $result);
        return count($result);
    }
    
    private function backtrack($nums, &$used, &$path, &$result) {
        if (count($path) == count($nums)) {
            if ($this->isSquareful($path)) {
                $result[implode(',', $path)] = true;
            }
            return;
        }
        
        for ($i = 0; $i < count($nums); $i++) {
            if ($used[$i] || ($i > 0 && $nums[$i] == $nums[$i - 1] && !$used[$i - 1])) continue;
            $path[] = $nums[$i];
            $used[$i] = true;
            $this->backtrack($nums, $used, $path, $result);
            array_pop($path);
            $used[$i] = false;
        }
    }
    
    private function isSquareful($perm) {
        for ($i = 0; $i < count($perm) - 1; $i++) {
            $sum = $perm[$i] + $perm[$i + 1];
            $root = (int)sqrt($sum);
            if ($root * $root != $sum) return false;
        }
        return true;
    }
}

Ставь 👍 и забирай 📚 Базу знаний