分区相等子集和的解决方案性能（DP，哈希表）

Question

我知道在stackoverflow中已经提出了一些相关的问题。然而，这个问题更多地与3种方法之间的性能差异有关。

问题是:给定一个只包含正整数的非空数组，找出该数组是否可以分成两个子集，使得两个子集的元素之和相等。https://leetcode.com/problems/partition-equal-subset-sum/

即[1，5，11，5] =真，[1，5，9] =假

通过解决这个问题，我尝试了3种方法：

>

方法1：动态规划。从上到下的递归记忆（结果：超出时间限制）：

def canPartition(nums):
    total, n = sum(nums), len(nums)
    if total & 1 == 1: return False
    half = total >> 1
    mem = [[0 for _ in range(half)] for _ in range(n)]
    def dp(n, half, mem):
        if half == 0: return True
        if n == -1: return False
        if mem[n - 1][half - 1]: return mem[n - 1][half - 1]
        mem[n - 1][half - 1] = dp(n - 1, half, mem) or dp(n - 1, half - nums[n - 1], mem)
        return mem[n - 1][half - 1]
    return dp(n - 1, half, mem)

方法2:动态编程。自下而上。(结果:2208毫秒被接受):

def canPartition(self, nums):
    total, n = sum(nums), len(nums)
    if total & 1 == 1: return False
    half = total >> 1
    matrix = [[0 for _ in range(half + 1)] for _ in range(n)]
    for i in range(n):
        for j in range(1, half + 1):
            if i == 0: 
                if j >= nums[i]: matrix[i][j] = nums[i]
                else: matrix[i][j] = 0
            else:
                if j >= nums[i]:
                    matrix[i][j] = max(matrix[i - 1][j], nums[i] + matrix[i - 1][j - nums[i]])
                else: matrix[i][j] = matrix[i - 1][j]
            if matrix[i][j] == half: return True
    return False

方法3：哈希表（字典）。结果（接受 172 毫秒）：

def canPartition(self, nums):
    total = sum(nums)
    if total & 1 == 0:
        half = total >> 1
        cur = {0}
        for number in nums:
            cur |= { number + x for x in cur} # update the dictionary (hashtable) if key doesn't exist
            if half in cur: return True
    return False

对于以上3种关于时间复杂性的方法，我真的不理解两件事：

< li >我认为方法1和方法2应该有相同的结果。两者都使用表格(矩阵)来记录计算的状态，但是为什么自底向上的方法更快呢？ < li >我不知道为什么方法3比其他方法快这么多。注:粗略看，方法3似乎是2的n次方方法，但它是用字典丢弃重复值，所以时间复杂度应该是T(n * half)。

Answer 1

你是对的，方法 1） 和 3） 具有相同的时间复杂度，html" target="_blank">方法 2 是背包的 DP 版本（0/1），方法 1 是分支和绑定版本。您可以通过任何背包启发式方法修剪树来改进方法一，但优化必须严格，例如，如果现有总和和级别 K 的剩余元素之和为

为什么方法1）和3）的运行时间不同，

[在某种程度上]

这与python中字典的实现有更多关系。字典是由Python解释器原生实现的，对它们的任何操作都将比任何需要首先解释且更频繁的操作都要快。此外，函数调用在python中开销更高，它们是对象。所以调用一个不是简单的缓冲堆栈和jmp/调用操作。

[在很大程度上]

要考虑的另一个方面是第三种方法的时间复杂度。对于方法3，时间复杂度可以是指数的唯一方法是每次迭代导致插入与当前迭代字典中一样多的元素。

  cur |= { number + x for x in cur}

上面的行应该加倍|cur|。

我认为像这样的系列是有可能的，

s={k， K²， K³，…， kⁿ，（

（其中K是素数

Answer 2

我对方法 1 与其他方法之间的差异的猜测是，由于递归，方法 1 需要生成更多的堆栈帧，这比仅仅分配矩阵和迭代条件更耗费系统资源。但如果我是你，我会尝试使用某种进程和内存分析器来更好地确定和确认正在发生的事情。方法 1 根据范围分配一个矩阵，但该算法实际上将迭代次数限制为可能要少得多，因为下一个函数调用跳转到数组元素减去的总和，而不是梳理所有可能性。

方法3仅取决于输入元素的数量和可以生成的和的数量。在每次迭代中，它将输入中的当前数字添加到所有先前可实现的数字上，仅将新数字添加到该列表中。例如，给定列表[500005000050000]，方法3最多迭代三次和：5000010000015000。但由于它取决于范围，方法2至少迭代75000*3次！

给定列表 [50000、50000、50000]，方法 1、2 和 3 生成以下迭代次数：15、225000 和 6。