Возврат, рекурсия, графики и много любви
Этот вопрос объединяет множество идей и концепций, которые мы рассмотрели. Делайте заметки о том, как мы переходим между различными компонентами решения. Переходы будут очень полезны в ваших интервью.
Будьте готовы танцевать.
Проблема
Учитывая массив различных целых чисел candidates и целевое целое число target, вернуть список всех уникальных комбинацийcandidates, где выбранные числа сумма равнаtarget. Вы можете возвращать комбинации в любом порядке.
Один и тот же номер может быть выбран из candidates неограниченного количества раз. Две комбинации уникальны, если частота хотя бы одного из выбранных чисел различна.
Тестовые примеры генерируются таким образом, чтобы количество уникальных комбинаций, суммирующихся до target, было меньше, чем 150 комбинаций для данного входа.
Пример 1:
Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]] Explanation: 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times. 7 is a candidate, and 7 = 7. These are the only two combinations.
Пример 2:
Input: candidates = [2,3,5], target = 8 Output: [[2,2,2,2],[2,3,3],[3,5]]
Пример 3:
Input: candidates = [2], target = 1 Output: []
Ограничения:
1 <= candidates.length <= 302 <= candidates[i] <= 40- Все элементы
candidatesразличны. 1 <= target <= 40
Вы можете протестировать свое решение здесь
Это бесплатное решение. Чтобы получать больше таких высококачественных сообщений, подпишитесь на информационный бюллетень и поднимите свою подготовку на новый уровень.
Подписан
Шаг 1: Чтение проблемы
Как только мы начинаем читать задачу, у нас в голове должен звенеть колокольчик. Фраза «список всех уникальных комбинацийcandidates’ является убедительным признаком того, что мы должны применить к алгоритму какой-то возврат. Это связано с тем, что для данной частичной конфигурации может быть несколько способов суммирования с целью. Единственный способ получить их все — вернуться назад.
Это одно понимание, но куда мы можем двигаться дальше? Давайте внимательно прочитаем задачу и попробуем смоделировать взаимодействие между различными компонентами нашего решения. На этом этапе мы не пытаемся решить проблему сразу. Мы просто пытаемся получить общее представление о нашей будущей системе. Мы не решаем, как работает система, а только то, что она делает. Как становится намного проще, когда мы разбираемся с этим.
Шаг 2: Моделирование системы
Итак, давайте смоделируем эту систему на высоком уровне. Мы знаем, что у нас есть цель и несколько кандидатов. Для любой заданной цели вы можете достичь разных состояний в своей программе, выбрав другую цель (7–2 — это другое значение, чем 7–3). Как только мы доберемся до нового состояния, процесс будет повторяться (мы можем выбрать новые состояния на основе подходящих кандидатов), что сделает этот процесс рекурсивным. Это не должно сильно шокировать, учитывая наличие возврата.
Итак, наша система имеет состояния и переходы, основанные на определенной операции. Похоже ли это на известную нам структуру данных? «Для тех, кто не знаком с описанной здесь структурой определения графов: всякий раз, когда вы можете смоделировать свою систему как серию состояний и переходов между этими состояниями, вы знаете, что можете решить вопрос с помощью графов.
В нашем случае цель и возможные комбинации цель-кандидат образуют состояния (узлы на нашем графике). Вычитание данного кандидата из узла образует переходы (ребра) системы. Если все это слишком абстрактно, взгляните на иллюстрацию очень похожей системы ниже:
Если это поможет, вы можете визуализировать систему в вопросе как Торговый автомат, так как у него почти идентичная механика. "Источник"
Итак, наша ситуация смоделирована в виде графа. Что мы делаем отсюда? Следующий шаг — просто выяснить, как мы будем проходить этот граф. Обратите внимание, что любой путь, ведущий от исходного целевого значения к 0, дает нам комбинацию, которая в сумме дает целевое значение. Итак, мы запускаем простой алгоритм обхода графа, реализуем поиск с возвратом и сохраняем все соответствующие значения.
Некоторые из вас могут дрожать при мысли об этом. В конце концов, реализация этих концепций является одной из самых сложных задач, которые вы можете ожидать. Но помните, шаг за шагом. Используя методы, которые я показывал здесь много раз, мы будем утверждать свое превосходство в этом вопросе (и наших интервьюеров).
Это будешь не ты. Я обещаю.
Шаг 3: Определение правильной механики обхода
Следующая задача состоит в том, чтобы выяснить правильный алгоритм обхода. Мы знаем, что наша текущая система не взвешена (один набор сумм не лучше другого), поэтому мы знаем, что наш обход будет либо BFS, либо DFS. Как мы можем выбрать?
Еще раз, у этого культа есть ответы, которые вам нужны. Несколько месяцев назад я сделал пост о том, как можно выбрать правильный алгоритм графа, исходя из различных деталей задачи. Исходя из этого, мы будем выбирать DFS. Почему ты спрашиваешь? Обратитесь к следующему отрывку-
Посещение полного графа: для задач, где мы должны учитывать весь граф (инопланетный словарь, обнаружение цикла и т. д.), тогда DFS станет вашим лучшим другом. Требуется меньше памяти.
Основное преимущество BFS заключается в задачах, связанных с кратчайшим путем. Однако здесь это не рассматривается. Мы все равно пройдем все пути. Таким образом, эффективность памяти играет здесь большую роль. Убедитесь, что вы указываете на своего интервьюера. В противном случае я найду твой дом и прослежу, чтобы это проникло в твою душу.
Нам нужно было выполнить 3 задания. Один упал.
Итак, мы запускаем простой алгоритм обхода графа, реализуем поиск с возвратом и сохраняем все соответствующие значения.
Время закругляться. Я должен заняться скалолазанием. Какие виды деятельности вы любите делать, когда вас тошнит от экрана? Дайте мне знать. Мне было бы интересно услышать об этом.
Шаг 4: Соединяем все части вместе
У нас есть большинство отдельных компонентов этой головоломки. Пора начать их интегрировать.
Обычно эти проблемы проще всего решить, используя глобальную переменную для отслеживания всех комбинаций. Это отличный способ отслеживать вычисления, происходящие в различных кадрах стека. Обычно полезно проводить всю рекурсию во вспомогательной функции, чтобы ограничить побочные эффекты рекурсии. Это дает нам следующий скелет-
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
def dfs(i, cur, total):
#something something
dfs(0, [], target)
return res
Так как же нам положить мясо на кости? К счастью, я уже поделился здесь своим шаблоном для простого написания рекурсивных функций. Шаблон выглядит следующим образом:
- Проверьте случаи прекращения.У нас есть два базовых случая. Во-первых, если мы достигнем суммы 0 (успех). Во-вторых, у нас есть случаи отказа. Я оставлю это вам, чтобы понять их (не волнуйтесь, полный код, как обычно, публикуется в конце).
- Выполнить обработку. Как только мы обработали базовые варианты, мы переходим к следующему шагу. Мы хотим облегчить прыжки назад. Это включает в себя добавление кандидата с нашим заданным индексом в наш набор кандидатов.
cur.append(candidates[i])
- Перейдем к рекурсивному случаю. Теперь мы готовы к нашему рекурсивному ходу. Этот шаг повторяется дважды, так как мы исследуем несколько путей.
dfs(i, cur, total - candidates[i]) #reset the side effects here dfs(i + 1, cur, total)
- Эта структура немного отличается от обычной. Причина в том, что в подобных вопросах мы хотим рассмотреть два случая. 1- Мы использовали значение в нашем текущем индексе в нашем решении. 2- Мы пропустили этот индекс и пошли дальше. Два рекурсивных вызова обрабатывают оба этих случая.
- Сбросить побочные эффекты. Заполните это самостоятельно и двигайтесь дальше. Я не хочу лишать вас драгоценной практики.
Чтобы понять значение каждого шага, обязательно прочитайте эту статью. Это поможет вам понять теорию, лежащую в основе шаблона, и поможет вам больше, чем просто слепое копирование.
Если вы гладко прошли каждый шаг, ваш код должен быть готов к работе. Посмотрим на окончательное решение.
Шаг 5: Кодирование вещей.
Собрав все воедино, получаем вот что:
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
def dfs(i, cur, total):
if total == 0:
res.append(cur.copy())
return
if i >= len(candidates) or total < 0:
return
cur.append(candidates[i])
dfs(i, cur, total - candidates[i])
cur.pop()
dfs(i + 1, cur, total)
dfs(0, [], target)
return res
Считайте, что слона съели.
Понравился пост? Ненавидеть это? Хотите поговорить со мной о вашем крипто-портфеле? Получить мои прогнозы на PPV UCL или MMA? Хотите подробный анализ лучших брендов шоколадного молока? Свяжитесь со мной, ответив на это письмо, в комментариях или воспользовавшись ссылками ниже.
Оставайтесь в сознании,
Иди всех убей,
Деванш ❤
Свяжитесь со мной по:
Небольшие фрагменты о технологиях, искусственном интеллекте и машинном обучении здесь
Инстаграм: https://www.instagram.com/iseethings404/
Напишите мне в Твиттере: https://twitter.com/Machine01776819
Мой LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
Мой контент:
Читайте мои статьи: https://rb.gy/zn1aiu
Мой Ютуб: https://rb.gy/88iwdd
