➡ Стартуем тему Backtracking

Представь, что ты оказался в огромном замке, полном дверей, коридоров и развилок. Твоя цель — найти комнату с сокровищем. У тебя с собой блокнот и карандаш, но нет карты.

Каждый раз, когда ты доходишь до развилки, ты записываешь в блокнот:

"Я сейчас в коридоре A, и уже пошёл в дверь 1 из 3 возможных."

Если за этой дверью тупик — ты возвращаешься назад, смотришь в блокнот и говоришь:

"Хм, я был в коридоре A и пробовал дверь 1. Попробую теперь дверь 2."

Идёшь туда, снова записываешь шаг, и так далее.

Так и работает Backtracking в программировании:
▫ты пробуешь решение
▫если оно не подходит — возвращаешься назад, отменяешь выбор и пробуешь другое
▫ты не забываешь, где был, и всегда можешь шагнуть обратно, чтобы попробовать что-то другое

#backtracking

🟡Medium
2698. Find the Punishment Number of an Integer

Company: 🔍📱📕

📝Дано число n, верните номер наказания.

Номер наказания для n определяется, как сумма квадратов всех целых чисел i, таких, что:

➖1 <= i <= n
➖десятичное представление i * i можно разбить таким образом, что сумма частей разбиения будет равна i

💡: пройди все числа от 1 до n и для каждого перебери все способы разрезать число по цифрам, возвращаясь назад, если их сумма превышает нужное значение

#leetcode2698 | #medium #backtracking

🟡Medium
1079. Letter Tile Possibilities

Company: 🏢📱📱

📝Дана строка tiles, состоящая только из заглавных букв.

Верните количество возможных непустых последовательностей, которые вы можете составить, используя буквы tiles

💡: рекурсивно составляйте все возможные комбинации, используя массив частот символов

#leetcode1079 | #medium #backtracking

🟡Medium
47. Permutations II

Company: 📱📱🅰️

📝Дан целочисленный массив, который может содержать дубликаты. Верните все возможные уникальные перестановки в любом порядке

💡: отсортируйте массив и пропускайте одинаковые элементы на одном уровне рекурсии, чтобы избежать дубликатов в перестановках

#leetcode47 | #medium #backtracking

🟡Medium
306. Additive Number

Company: 📱

📝Дана строка, содержащая только цифры, вернуть true, если она является аддитивным числом.

Аддитивное число — это строка, цифры которой могут образовывать допустимую аддитивную последовательность:

▫ содержит не менее трёх чисел
▫ каждое последующее число в последовательности должно быть суммой двух предыдущих (за исключением первых двух)
▫числа в последовательности не могут иметь начальных нулей

💡: переберите все возможные комбинации первых двух чисел и продолжайте разбиение строки, если следующее число равно их сумме

#leetcode306 | #medium #backtracking

🟡Medium
1415. The k-th Lexicographical String of All Happy Strings of Length n

Company: 🔍📱🏢

📝Даны два целых числа n и k. Рассмотрите отсортированный в лексикографическом порядке список всех счастливых строк длины n.

Верните k-ю строку этого списка или пустую строку, если количество счастливых строк меньше.

Счастливая строка — это строка, которая:
▫состоит только из букв набора ['a', 'b', 'c']
▫не содержит двух рядом стоящих одинаковых символов

Список счастливых строк для примера 3:

["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"]

💡: рекурсивно стройте строки, добавляя буквы от 'a' к 'c', избегая одинаковых соседних символов

#leetcode1415 | #medium #backtracking

🔴Hard
51. N-Queens

Company: 🔍📕📱

📝Дано целое число n, найдите все различные решения головоломки с n ферзями.

Задача об n ферзях — это расстановка n ферзей на n x n шахматной доске таким образом, чтобы никакие два ферзя не атаковали друг друга.

Каждое решение должно содержать отдельную конфигурацию доски с размещением n ферзей, где 'Q' и '.' обозначают ферзя и пустое место соответственно

💡: используйте backtracking, ставя ферзя построчно и одновременно отслеживая занятые столбцы и диагонали

#leetcode51 | #hard #backtracking

🔴Hard
679. 24 Game

Company: 🔍🚖📱

📝Дан массив целых чисел cards длиной 4, где каждая карта содержит число от 1 до 9.

Вам нужно составить из чисел на этих карточках математическое выражение, используя операторы ['+', '-', '*', '/'] и скобки (), чтобы получить значение 24.

При этом действуют следующие правила:

▫Оператор деления '/ 'представляет собой действительное деление, а не целочисленное

Например, 4 / (1 - 2 / 3) = 4 / (1 / 3) = 12

▫Каждая операция применяется только между двумя числами (унарные минусы запрещены)
▫Числа нельзя объединять

Например, если cards = [1, 2, 1, 2], то выражение "12 + 12" недопустимо

Верните true, если возможно получить выражение, равное 24

💡: попробуйте перебрать все пары чисел и заменить их результатом арифметической операции, рекурсивно сводя задачу к одному числу

#leetcode679 | #hard #backtracking

🔴Hard
37. Sudoku Solver

Company: 🔍📕📱

📝Напишите алгоритм, который решает головоломку Судоку, заполняя все пустые клетки.

Игровое поле представлено в виде двумерного массива символов, где каждая клетка содержит либо цифру '1'–'9', либо символ '.', обозначающий пустую клетку.

Условия решения:
▫В каждой строке — все цифры 1–9 без повторов
▫В каждом столбце — все цифры 1–9 без повторов
▫В каждом блоке 3×3 — все цифры 1–9 без повторов

💡: при размещении числа, сразу исключайте его из строки, столбца и блока, чтобы сократить поиск

#leetcode37 | #hard #backtracking