Leetcode — задача о сумме комбинаций в Python

Я строю логику для задачи Leetcode — Combination Sum. Вот ссылка на проблему. В проблеме говорится:

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

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

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

Пример 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

Объяснение:
2 и 3 являются кандидатами, а 2 + 2 + 3 = 7. Обратите внимание, что 2 можно использовать несколько раз.
7 — кандидат, а 7 = 7.
Это единственные две комбинации.

Мой текущий ответ принят платформой. Код выглядит следующим образом.

def help(self, i, s, c, t,arr,ans):
    if s == t:
        ans.append(arr)
        return
    if i==len(c) or s>t:
        return
    self.help(i+1,s,c,t,arr,ans)

    self.help(i,s+c[i],c,t,arr + [c[i]],ans)
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    ans = []
    i=0
    self.help(i,0,candidates, target, [],ans)
    return ans

Но когда я меняю два рекурсивных вызова функции в функции справки на что-то вроде этого, это терпит неудачу.

def help(self, i, s, c, t,arr,ans):
    if s == t:
        ans.append(arr)
        return
    if i==len(c) or s>t:
        return
    self.help(i+1,s,c,t,arr,ans)
    arr.append(c[i])
    self.help(i,s+c[i],c,t,arr,ans)
    arr.pop()
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    ans = []
    i=0
    self.help(i,0,candidates, target, [],ans)
    return ans

Я не понимаю разницы. В обоих этих блоках кода я делаю практически одно и то же. Тогда почему при добавлении и извлечении происходит сбой, в то время как другой принимается?

Нам было бы проще, если бы вы использовали осмысленные имена переменных, а не просто отдельные символы.

Barmar 03.06.2024 17:16

Попробуйте напечатать arr перед добавлением и после добавления и посмотрите, совпадают ли они.

Barmar 03.06.2024 17:21

Да, они одинаковы. Я только что узнал, что если я сделаю ans.append(arr[:]) вместо ans.append(arr), это просто волшебным образом сработает.

vikram sah 03.06.2024 17:33

Верно, потому что arr.append и arr.pop изменяют список на месте, поэтому вы возвращаете списки, которые вы сохранили в ans.

Barmar 03.06.2024 17:43

Хорошо. Кажется, я не могу полностью осознать это. Можете ли вы дать объяснение, которое выявляет разницу в том, какие значения отправляются при вызове функции в обоих случаях? Я думаю, что это будет тот ответ, который я ищу здесь

vikram sah 03.06.2024 17:49
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
1
5
114
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

В вашей первой версии вы передаете новый список при каждом рекурсивном вызове, потому что arr + [c[i]] создает новый список. Таким образом, каждый элемент, добавленный к ans, представляет собой отдельный список.

Во второй версии вы продолжаете изменять один и тот же список, используя arr.append(c[i]) и arr.pop(). Таким образом, все элементы ans являются ссылками на один и тот же список.

Если вы используете ans.append(arr[:]), вы делаете копию этого списка, поэтому последующие arr.pop() на него не влияют.

Другие вопросы по теме