为什么以下两种解决方案的时间复杂性如此不同

Question

我试图解决Leetcode问题-https://leetcode.com/problems/partition-equal-subset-sum/.我提出了一个备忘录化的解决方案，但从未被接受，因为显然它花了太多时间。以下是解决方案。

class Solution{
public:
bool canPartition(vector<int>& nums){
int totalSum = 0;
for(auto value : nums)
totalSum += value;
if(totalSum%2 == 1)
return false;
return helper(nums, totalSum/2, 0);
}
private:
bool helper(vector<int> nums, int totalSum, int index){
if(totalSum == 0)
return true;
if(totalSum < 0)
return false;
if(index == nums.size())
return false;
// Check in the cache
pair<int, int> key = make_pair(totalSum, index);
if(cache.count(key)){
//cout << "Cache hit!n";
return cache[key];
}
// Include this
bool include = helper(nums, totalSum-nums[index], index+1);
// Exclude this
bool exclude = helper(nums, totalSum, index+1);
cache[key] = include || exclude;
return cache[key];
}
map<pair<int, int>, bool> cache;
};

经过一段时间的尝试，我做了一个小的更改，不再使用"include"one_answers"exclude"布尔值，我只做了以下操作，时间复杂性显著提高，从1000ms降至0ms。我很困惑为什么会发生这种事？为什么使用两个布尔然后将结果存储在地图中比不使用它们时慢得多？

cache[key] = helper(nums, totalSum-nums[index], index+1) || helper(nums, totalSum, index+1);

有人能在这里启发我吗？对此相当困惑。

Answer 1

第一个版本调用helper两次，一次用于include，一次为exclude。第二个版本，因为它使用了逻辑或运算符，所以如果第一个helper为true，则不会调用第二个helper。换句话说，如果include为true，则不会进行exclude调用，因为它不会更改表达式的结果。

另一个性能命中是helper的nums参数。您不会在函数中对其进行任何更改，因此可以将其作为const vector<int> &nums传递，以避免对数组的整个内容进行不必要的复制。canPartition也可以将其参数作为常量引用，因为您不修改它