Задача: 473. Matchsticks to Square
Сложность: 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 {
    private $nums;
    private $sums;
    private $possibleSquareSide;

    function __construct() {
        $this->sums = array_fill(0, 4, 0);
    }

    private function dfs($index) {
        if ($index == count($this->nums)) {
            return $this->sums[0] == $this->sums[1] && $this->sums[1] == $this->sums[2] && $this->sums[2] == $this->sums[3];
        }

        $element = $this->nums[$index];

        for ($i = 0; $i < 4; $i++) {
            if ($this->sums[$i] + $element <= $this->possibleSquareSide) {
                $this->sums[$i] += $element;
                if ($this->dfs($index + 1)) {
                    return true;
                }
                $this->sums[$i] -= $element;
            }
        }

        return false;
    }

    function makesquare($nums) {
        if (empty($nums)) {
            return false;
        }

        $perimeter = array_sum($nums);
        $this->possibleSquareSide = intval($perimeter / 4);
        if ($this->possibleSquareSide * 4 != $perimeter) {
            return false;
        }

        rsort($nums);
        $this->nums = $nums;
        return $this->dfs(0);
    }
}

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