Сложность: medium
Дано целочисленный массив спичек, где matchsticks[i] — это длина i-й спички. Необходимо использовать все спички для создания одного квадрата. Нельзя ломать никакую спичку, но можно соединять их, при этом каждая спичка должна быть использована ровно один раз.
Вернуть true, если можно составить квадрат, и false в противном случае.
Пример:
Input: matchsticks = [1,1,2,2,2]
Output: true
Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.
👨💻 Алгоритм:
1⃣Определяем рекурсивную функцию, которая принимает текущий индекс обрабатываемой спички и количество сторон квадрата, которые уже полностью сформированы. Базовый случай для рекурсии: если все спички использованы и сформировано 4 стороны, возвращаем True.
2⃣Для текущей спички рассматриваем 4 варианта: она может быть частью любой из сторон квадрата. Пробуем каждый из 4 вариантов, вызывая рекурсию для них.
3⃣Если какой-либо из рекурсивных вызовов возвращает True, возвращаем True, в противном случае возвращаем False.
😎 Решение:
class Solution {
var nums: [Int] = []
var sums: [Int] = [0, 0, 0, 0]
var possibleSquareSide: Int = 0
func dfs(_ index: Int) -> Bool {
if index == nums.count {
return sums[0] == sums[1] && sums[1] == sums[2] && sums[2] == sums[3]
}
let element = nums[index]
for i in 0..<4 {
if sums[i] + element <= possibleSquareSide {
sums[i] += element
if dfs(index + 1) {
return true
}
sums[i] -= element
}
}
return false
}
func makesquare(_ nums: [Int]) -> Bool {
if nums.isEmpty {
return false
}
let perimeter = nums.reduce(0, +)
possibleSquareSide = perimeter / 4
if possibleSquareSide * 4 != perimeter {
return false
}
self.nums = nums.sorted(by: >)
return dfs(0)
}
}Ставь 👍 и забирай 📚 Базу знаний