Leetcode # 377 Combination Sum IV, Неожиданное поведение в моем коде

Question

Я занимался этой проблемой, обнаруженной по адресу: https://leetcode.com/problems/combination-sum-iv/

Вот мой код:

class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:

    length = len(nums)
    count = 0 
    tracker = []
    result = []

    def backtrack(targetLeft: int) -> None:
        nonlocal count

        if targetLeft == 0:
            print(tracker)
            result.append(tracker)
            count += 1
            return

        elif targetLeft > 0:
            for number in nums:
                if targetLeft - number < 0:
                    continue
                tracker.append(number)
                backtrack(targetLeft - number)
                tracker.pop()

        return


    backtrack(target)
    print(result)
    return count

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

[1, 1, 1, 1] 
[1, 1, 2]
[1, 2, 1]
[1, 3]
[2, 1, 1]
[2, 2]
[3, 1]
[[], [], [], [], [], [], []]

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

Answer 1

Эта задача имеет простое линейное решение O (N), где N - сумма, которую вы пытаетесь достичь. Дело в том, что вам не нужно генерировать все комбинации для их подсчета.

1. подсчитайте, сколько способов достичь N = 1 (ответ: 1, потому что очевидно)
2. посчитайте, сколько способов достичь N = 2 (ответ: 2, один из N = 1, один из нуля)
3. подсчитайте, сколько способов достичь N = 3, 4, 5, 6 и т. д. на основе ваших предыдущих результатов, в основном суммируйте результаты для N-1, N-2 и всех этих чисел, которые у вас есть.
4. прибыль!