Leetcode #377 组合总和 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，因为很明显(
计算达到 N=
2. 2 的方法有多少种(答案：2，一个来自 N=1，一个来自零位(
数
3. 一数达到N=3、4、5、6等的方法有多少种，根据你之前的结果，基本上把N-1、N-2的结果和你拥有的所有这些数字相加。
4. 利润！