Я строю логику для задачи 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
Я не понимаю разницы. В обоих этих блоках кода я делаю практически одно и то же. Тогда почему при добавлении и извлечении происходит сбой, в то время как другой принимается?
Попробуйте напечатать arr перед добавлением и после добавления и посмотрите, совпадают ли они.
Да, они одинаковы. Я только что узнал, что если я сделаю ans.append(arr[:]) вместо ans.append(arr), это просто волшебным образом сработает.
Верно, потому что arr.append и arr.pop изменяют список на месте, поэтому вы возвращаете списки, которые вы сохранили в ans.
Хорошо. Кажется, я не могу полностью осознать это. Можете ли вы дать объяснение, которое выявляет разницу в том, какие значения отправляются при вызове функции в обоих случаях? Я думаю, что это будет тот ответ, который я ищу здесь






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