✅ Решение задачи 46

Time: O(n!)
Space: O(n)

📝 Идея
▫️Проходим по массиву, для каждого элемента рекурсивно перебирая все возможные варианты оставшихся
▫️Базовым случаем является равенство длины текущей перестановки и длины массива
▫️В результате получаем следующую последовательность:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]

#solution46

🟡 Medium
39. Combination Sum

📃 Учитывая массив различных целых чисел и значение target, вернуть список всех уникальных комбинаций (в любом порядке), где выбранные числа в сумме дают target.

Один и тот же номер может быть выбран неограниченное количество раз. Две комбинации являются уникальными, если частота хотя бы одно из выбранных чисел отличается.

Подсказка: рекурсивно используйте каждый элемент максимальное количество раз, затем удаляйте его и переходите к следующему

53/200
#medium
#leetcode39

✅ Решение задачи 39

Time: O(2^n)
Space: O(n)

📝 Идея
▫️Для каждого элемента рекурсивно набираем его максимальное количество раз, пока не выйдем за пределы target
▫️Затем удаляем последний элемент в текущем варианте и делаем те же действия для следующего элемента

#solution39

🟡 Medium
90. Subsets II

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

Набор решений не должен содержать повторяющихся подмножеств.

Подсказка: отсортируйте массив для избежания повторяющихся подмножеств

54/200
#medium
#leetcode90

✅ Решение задачи 90

Time: O(2^n)
Space: O(n)

📝 Идея
▫️Перебираем все возможные варианты, используя рекурсию и удаляя затем последний элемент
▫️Так как массив отсортирован, можно легко избежать повторяющихся подмножеств, делая проверку на равенство значений предыдущего и текущего элементов
▫️При этом условие i > start позволяет брать дублирующиеся значения в рекурсивном вызове для составления всех вариантов

#solution90

🟡 Medium
79. Word Search

📃 Дана сетка символов и слово word, вернуть true, если word существует в сетке.

Слово может быть составлено из букв последовательно соседних ячеек, где соседними являются ячейки по горизонтали или вертикали. Одна и та же ячейка не может быть использована более одного раза.

Подсказка: для каждого элемента матрицы рекурсивно проверяйте все стороны на возможное продолжение слова

55/200
#medium
#leetcode79

✅ Решение задачи 79

Time: O(mn4^L)
Space: O(L)

📝 Идея
▫️Проходимся по сетке и используем каждый символ, как возможное начало слова
▫️Функция dfs рекурсивно реализует поиск следующего символа в слове, проверяя все ячейки вокруг текущей позиции
▫️Пометка board[i][j] = '*' необходима для того, чтобы не использовать один символ дважды

#solution79

🟡 Medium
40. Combination Sum II

📃 Дан целочисленный массив и значение target, вернуть все уникальные комбинации, в которых сумма чисел составляет target.

Каждое число может быть использовано в комбинации только один раз.

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

56/200
#medium
#leetcode40

✅ Решение задачи 40

Time: O(2^n)
Space: O(2^n)

📝 Идея
▫️Перебираем все возможные варианты, используя рекурсию и удаляя затем последний элемент
▫️Так как массив отсортирован, можно легко избежать повторяющихся комбинаций, делая проверку на равенство значений предыдущего и текущего элементов
▫️При этом условие i > start позволяет брать дублирующиеся значения в рекурсивном вызове для составления всех вариантов
▫️Стоит отметить, что прерывание цикла после выполнения условия (nums[i] > target) ускоряет код в 2 раза

#solution40

🟡 Medium
17. Letter Combinations of a Phone Number

📃 Дана строка, содержащая цифры от 2-9 включительно, вернуть все возможные комбинации букв, которые может представлять число. Верните ответ в любом порядке.

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

57/200
#medium
#leetcode17

✅ Решение задачи 17

Time: O(3^n*4^m)
Space: O(3^n*4^m)

📝 Идея
▫️Сопоставление цифр и букв храним в HashMap
▫️Используя подход backtrack, перебираем каждый символ текущего набора и добавляем новый из следующего
▫️Когда длина текущей комбинации равна длине строки цифр, добавляем ее в результат

#solution17

🟡 Medium
131. Palindrome Partitioning

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

Подсказка: реализуйте подход backtrack c проверкой на палиндромную строку

58/200
#medium
#leetcode131

✅ Решение задачи 131

Time: O(2^n)
Space: O(2^n)

📝 Идея
▫️Используем подход backtrack, рекурсивно перебирая возможные разбиения строки, при этом делая проверку на палиндромность подстроки функцией isPalindrom
▫️Если index равен длине строки, значит все подстроки прошли проверку на палиндромность и можно добавлять в ответ полученное разбиение

#solution131

🟢 Easy
70. Climbing Stairs

📃 Вы поднимаетесь по лестнице на вершину n.
Каждый раз вы можете подняться либо на 1, либо на 2 ступеньки. Сколькими различными способами вы можете подняться на вершину?

Подсказка: с каких ступенек вы можете подняться на n-ую?

59/200
#easy
#leetcode70

✅ Решение задачи 70

Time: O(n)
Space: O(n)

📝 Идея
▫️Используем подход "динамическое программирование", то есть когда задача раскладывается на более простую
▫️На i-ую ступеньку можно прийти только двумя способами: с предыдущей и с (i-2)-ой
▫️Соответственно, количество способов подняться на i-ую ступеньку будет равняться сумме способов с i-1 и i-2

#solution70

🟡 Medium
198. House Robber

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

Подсказка: для каждого элемента проверяйте какую максимальную сумму денег, которую здесь возможно получить

60/200
#medium
#leetcode198

✅ Решение задачи 198

Time: O(n)
Space: O(1)

📝 Идея
▫️Начиная со 2-го элемента смотрим какую максимальную сумму можно получить, проверяя стоит ли грабить этот дом или пойти дальше
▫️Для этого берем максимум из полученной суммы в предыдущей ячейке и суммы, которую можно получить складывая текущую ячейку и ячейку n-2
▫️В итоге, пройдя весь цикл, в последней ячейке будет ответ на задачу

#solution198

🟡 Medium
215. Kth Largest Element in an Array

📃 Дан массив целых чисел и целое число k, вернуть наибольший k-ый элемент массива.
Необходимо решить задачу без использования сортировки.

Подсказка: используйте PriorityQueue

61/200
#medium
#leetcode215

✅ Решение задачи 215

Time: O(nlogn)
Space: O(n)

📝 Идея
▫️Для решения используем ProrityQueue, данная структура данных добавляет элементы за log(n), при этом позволяя за O(1) найти минимум
▫️Поскольку задача найти максимальное значение, сохраняем все элементы со знаком минус
▫️Далее удаляем элементы, пока k > 1, чтобы в результате сверху остался k-ый максимальный элемент

#solution215

🟢 Easy
746. Min Cost Climbing Stairs

📃 Вам дан целочисленный массив cost, где cost[i] — стоимость шага на лестнице. После оплаты стоимости вы можете подняться на 1 или 2 ступеньки.
Вы можете начать движение либо с 0, либо с 1 элемента.
Верните минимальную стоимость, чтобы достичь верхнего этажа.

Подсказка: используйте динамическое программирование

62/200
#easy
#leetcode746

✅ Решение задачи 746

Time: O(n)
Space: O(1)

📝 Идея
▫️Для каждого элемента ищем минимальный способ сюда попасть, выбирая минимум из стоимости элементов i-1 и i-2
▫️Пройдя весь цикл, выбираем минимум из последних двух элементов, так как достичь верхнего этажа можно сделав 1 или 2 шага

#solution746