java - 分区相等子集和自顶向下TLE

Question

我正在解决 Partition Equal Subset Sum的 leetcode。

问题状态:

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

Each of the array element will not exceed 100.
The array size will not exceed 200.

我写的代码如下

class Solution {
public boolean canPartition(int[] nums) {
    int sum=0;
    for(int i=0;i<nums.length;i++)
    {
        sum=sum+nums[i];
    }
    if(sum%2!=0)
    {
        return false;
    }

    int target=sum/2;
    return helper(nums,target,nums.length);

}
boolean helper(int nums[],int sum,int n)
{
    if(sum==0)
    {
        return true;
    }
    if(sum<0)
    {
        return false;
    }
    if(n==0)
    {
        return false;
    }
    return helper(nums,sum-nums[n-1],n-1)||helper(nums,sum,n-1);
}


 }

注意我没有包含条件

if(sum<nums[n-1])
{
return false;
}

在我已经包含的基本情况下

if(sum<0)
    {
        return false;
    }

这与它只会再添加 1 个递归调用然后返回 false 是一回事。

此代码适用于 89 个测试用例，但给出 TLE 错误

[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,100]

现在如果修改相同的代码并包含

if(sum<nums[n-1])
    {
    return false;
    }

并删除

if(sum<0)
    {
        return false;
    }

即

class Solution {
public boolean canPartition(int[] nums) {
    int sum=0;
    for(int i=0;i<nums.length;i++)
    {
        sum=sum+nums[i];
    }
    if(sum%2!=0)
    {
        return false;
    }

    int target=sum/2;
    return helper(nums,target,nums.length);

}
boolean helper(int nums[],int sum,int n)
{
    if(sum==0)
    {
        return true;
    }

    if(n==0)
    {
        return false;
    }
    if(nums[n-1]>sum)
    {
        return false;
    }

    return helper(nums,sum-nums[n-1],n-1)||helper(nums,sum,n-1);
}
}

代码运行良好并通过了所有测试用例。

既然两个代码都是一样的，那一个额外的递归调用怎么会给我 TLE？还有别的吗？

Answer 1

测试用例真的很薄弱。第一个应该得到 TLE，因为你没有使用动态编程，而是执行了一个简单的回溯。第二个应该得到 WA。如果您使用记忆化，您的复杂度将是 O( totalSum * arraySize) 但您的代码的复杂度是 O(2 ^ arraySize)。

现在观察您在每个州都有两个选择。要么选择元素，要么不选择。即使此条件为真 if(nums[n-1]>sum) ，第二个选项也是有效的 - 继续不选择项目。但是您的第二个代码忽略了该条件的两种情况，将调用减少到您的解决方案花费不到 1 毫秒的时间，这比大多数正确的解决方案都快。由于第二个解决方案没有反测试用例，因此它通过了。