LeetCode 416：递归记忆化解法超时原因咨询

我在解决LeetCode 416题（分割等和子集）时遇到了问题，题目要求：给定只含正整数的非空数组nums，判断能否将其分割为两个元素和相等的子集。

我的递归实现（带缓存优化） #

我尝试用带@cache的递归解法优化以避免超时，代码如下：

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        totalSum = sum(nums) 
        if totalSum % 2 == 1:
            return False
        @cache
        def helper(index, setOne):
            if setOne < 0:
                return False
            if setOne == 0:
                return True
            for x in range(index, len(nums)):
                if helper(x +1, setOne - nums[x]):
                    return True
            return False
        return helper(0,totalSum // 2)

优化后通过的测试用例从36个增至74个，但仍超时。

参考的AC递归实现 #

我查看了一份Accepted方案，参考代码如下：

class Solution:
    def canPartition(self, nums):
        @cache
        def subsetSum(s, i):
            if s == 0: return True
            if i >= len(nums) or s < 0: return False
            return subsetSum(s-nums[i], i+1) or subsetSum(s, i+1)
        total_sum = sum(nums)
        return total_sum & 1 == 0 and subsetSum(total_sum // 2, 0)

疑问点 #

我认为自身解法的时间复杂度应与参考方案一致，但实际效率更低，猜测可能遗漏了需要记忆化的变量，希望得到原因分析。

复杂度分析疑问 #

最初我认为自己代码的时间复杂度是O(n*2ⁿ)，后来分析觉得是O(2ⁿ)，因为循环本质是对每个索引做选或不选的二元选择，请问该分析是否正确？

后续尝试 #

采纳建议修改代码后，效率显著提升但仍超时，猜测或与LeetCode的判定机制有关。

内容的提问来源于stack exchange，提问作者just-an-average-programmer