在抛出 'std：：length_error' 实例后调用的终止，what()： 无法创建大于 max_size() 的 std：：vector

Question

我解决了416。分区等于子集和问题

int sum = 0;
for(auto num : nums) sum += num;  // get sum

if(sum%2 == 1) return false;  // not possible case - in odd sum

sum /= 2;  // first halve the sum
vector<bool> table(sum+1, false);  // create 1-d bool array, initialize false
table[0] = true;  // mark starting true
for(auto num : nums)  // for each num
{
for(int i=sum; i>=num; i--)  // from sum till it is greater than or num
{
table[i] = table[i] or table[i-num];  // Or with including this num or not
}
}
return table[sum]; 

我发现了类似的问题494。目标和，所以我试着用同样的概念来解决:

int sum = 0;
for(auto num : nums) sum += num;  // get sum        
if(sum < target or (sum + target)%2 == 1) return 0;  // not possible case - sum < target or newSum is odd

int newSum = (sum + target)/2;
vector<int> table(newSum+1, 0);
table[0] = 1;

for(auto num : nums)
{
for(int i = newSum; i>=num; i--)
{
table[i] = table[i] + table[i-num];
}
}
return table[newSum];

但是，有运行时错误:

terminate called after throwing an instance of 'std::length_error'
what():  cannot create std::vector larger than max_size()

我谷歌这个问题来解决它，但无法找到任何简单的解决方案，可以帮助理解我。你能帮我理解和解决这个问题吗?

Answer 1

正如Alan Birtles上面评论的那样:

int target也可以是负数，所以newSum

int newSum = (sum + target)/2;  // can be negative number
vector<int> table(newSum+1, 0);  // so you can not assigne negative size of a `vector` here.

解决方案:在赋给vector之前取newSum的绝对值，以确保向量的大小只为正，不为负。

int newSum = abs((sum + target)/2);  // take abs 
vector<int> table(newSum+1, 0);  // to make sure, size of vector is positive only, not negative.