用C++的蛮力法求解:求一个数组是否可以分割成元素和相等的两个子集。 输入:[1,5,11,5];输出:true。可以分割成 [1,5,5] 和 [11]。 输入:[1,2,5];输出:false。无法分割成元素和相等的两个子集。
时间: 2024-09-23 14:04:39 浏览: 25
c++分治法求解众数问题
5星 · 资源好评率100%
在C++中,你可以通过蛮力法(也称为暴力搜索或穷举法)来解决这个问题,即遍历所有可能的组合,并检查是否存在一种情况,使得一半的数组元素之和等于另一半的数组元素之和。以下是解决此问题的一种简单算法:
```cpp
#include <vector>
#include <algorithm>
bool can_split_equal_sum(std::vector<int>& nums) {
int total_sum = std::accumulate(nums.begin(), nums.end(), 0); // 计算数组总和
if (total_sum % 2 != 0) { // 如果总数不是偶数,不可能分成两组和相等
return false;
}
int half_sum = total_sum / 2; // 半数和
for (int i = 0; i < nums.size(); ++i) { // 遍历数组
int current_sum = 0;
for (int j = i; j < nums.size(); ++j) { // 从第i个元素开始尝试配对
current_sum += nums[j];
if (current_sum == half_sum) { // 找到匹配的一半,返回true
return true;
} else if (current_sum > half_sum) { // 当前部分和大于半数和,跳过剩余元素
break;
}
}
if (current_sum == half_sum) { // 如果当前循环找到另一半,说明找到了解决方案
return true;
}
}
return false; // 没有找到匹配,返回false
}
```
阅读全文