python - 子集总和 : Why is DFS + pruning faster than 2 for loop?

Question

本题是leetcode 416 Partition Equal Subset Sum.

#2 for loop, which got TLE
class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        nums.sort()
        allsum = sum(nums)
        if allsum % 2 == 1:
            return False
        subsets = {() : 0}
        temp = dict(subsets)
        for each in nums:
            for subset in subsets:
                new = temp[subset] + each
                if new * 2 == allsum:
                    return True
                elif new * 2 < allsum:
                    temp[tuple(list(subset) + [each])] = new
                else:
                    del temp[subset]
            subsets = dict(temp)
        return False

DFS + pruning:
class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        nums.sort()
        if sum(nums) % 2 != 0:
            return False
        else:
            target = sum(nums) / 2
        return self.path(nums, len(nums), target)

def path(self, nums, length, target):#DFS + pruning
    if target == 0:
        return True
    elif target < 0 or (target > 0 and length == 0):
        return False
    if self.path(nums, length - 1, target - nums[length - 1]):
        return True
    return self.path(nums, length - 1, target)

为什么 2 for 循环比 DFS 慢？他们都有剪枝，我觉得DFS的时间复杂度，也就是np问题，应该比2个for循环差吧？

Answer 1

仅仅因为您使用了两个循环并不意味着您的算法是 O(n²) 或多项式。算法的复杂度取决于每个循环执行了多少次。 在这部分代码中:

    for each in nums:
        for subset in subsets:
            ....

第一个循环将运行 n 次，因为 nums 的大小是 n 并且它不会改变。然而，subsets 的大小在每次迭代后都会增加 2 倍。所以你的第二个 for 循环的主体将执行 1 + 2 + 4 + 8 + 16 + 32 + ... + 2^n = 2^(n+1) 次。

所以你的算法在 O(2ⁿ) 中，甚至没有考虑昂贵的操作(复制 list 和 dicts) 你在第二个循环的主体中执行。

您的第二种方法(从技术上讲不是 DFS)在案例复杂性方面等同于您的第一种方法。它们都是 O(n²)。但是在第二种方法中，与第一种方法(复制 list 和 dict 等)相比，你做的额外工作更少。因此，您的第一种方法可能会运行得更快，但从长远来看并不重要。对于更大尺寸的输入，这两种方法都不够有效。

请注意，这是一个非常著名的问题，称为 Subset-sum这是NP-Complete。可以使用 Dynamic Programming 解决在 Pseudo-polynomial time .