时间戳

首页 > 解决方案 > Leetcode #377 组合总和 IV，我的代码中的意外行为

python - Leetcode #377 组合总和 IV，我的代码中的意外行为

问题描述

我正在做这个问题，发现于： 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]
[[], [], [], [], [], [], []]

它似乎生成了正确的组合，但是这些组合没有正确地附加到结果数组中。结果数组返回到一个空数组数组。我尝试手动浏览代码，但我不太确定导致这种情况发生的原因。

标签： pythonarraysrecursionbacktracking

解决方案

这个问题有一个简单的线性解 O(N)，其中 N -- 是你想要达到的总和。关键是，您不必生成所有组合来计算它们。

  1. 计算达到 N=1 的方法有多少（答案：1，因为很明显）
  2. 计算达到 N=2 的方法有多少（答案：2，一种来自 N=1，一种来自 0 pos）
  3. 数一下有多少种方法可以达到 N=3、4、5、6 等等，根据你之前的结果，基本上总结了 N-1、N-2 和所有这些数字的结果。
  4. 利润！

推荐阅读