Задача: 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 {
    func numSquarefulPerms(_ nums: [Int]) -> Int {
        var nums = nums.sorted()
        var used = Array(repeating: false, count: nums.count)
        var result = Set<[Int]>()
        var path = [Int]()
        backtrack(nums, &used, &path, &result)
        return result.count
    }
    
    private func backtrack(_ nums: [Int], _ used: inout [Bool], _ path: inout [Int], _ result: inout Set<[Int]>) {
        if path.count == nums.count {
            if isSquareful(path) {
                result.insert(path)
            }
            return
        }
        
        for i in 0..<nums.count {
            if used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) { continue }
            path.append(nums[i])
            used[i] = true
            backtrack(nums, &used, &path, &result)
            path.removeLast()
            used[i] = false
        }
    }
    
    private func isSquareful(_ perm: [Int]) -> Bool {
        for i in 0..<perm.count - 1 {
            let sum = perm[i] + perm[i + 1]
            let root = Int(sqrt(Double(sum)))
            if root * root != sum { return false }
        }
        return true
    }
}

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