给你一个数组,问你是否能将数组分成 4 等份,即每一份的数字总和都相等,你不能拆分数组中的数字,如果能得到有效划分就返回 true,否则返回 false。用c++语言写出程序
时间: 2023-11-27 17:04:30 浏览: 53
好的,我可以帮你解决这个问题。这个问题可以用递归来解决。具体的步骤如下:
1. 首先,计算整个数组的总和 sum,如果 sum 不能被 4 整除,那么直接返回 false。
2. 然后,我们定义一个辅助函数 helper,该函数将递归地计算数组的四个子集的总和是否都等于 sum/4。这个函数有 4 个参数:数组 nums、当前处理的子集的索引 index、当前子集的总和 curSum,以及目标子集的总和 targetSum(即 sum/4)。
3. 在 helper 函数中,我们首先检查我们是否已经递归处理了 4 个子集。如果是,则返回 true。
4. 然后,我们从当前索引 index 开始循环数组 nums。对于每个数,我们将其加入当前子集的总和 curSum 中。如果 curSum 小于 targetSum,则递归调用 helper 函数来处理下一个数。
5. 如果 curSum 等于 targetSum,则我们递归调用 helper 函数来处理下一个子集,同时将索引 index 重置为 0,并将 curSum 重置为 0。
6. 如果 curSum 大于 targetSum,则直接返回 false。
7. 最后,如果我们递归处理完 4 个子集后仍然没有返回 true,则说明无法将数组分成 4 等份,返回 false。
下面是代码实现:
```c++
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % 4 != 0) return false;
int targetSum = sum / 4;
vector<bool> visited(nums.size(), false);
return helper(nums, 0, targetSum, 0, 0, visited);
}
bool helper(vector<int>& nums, int index, int targetSum, int curSum, int count, vector<bool>& visited) {
if (count == 4) return true;
if (curSum == targetSum) return helper(nums, 0, targetSum, 0, count + 1, visited);
if (curSum > targetSum) return false;
for (int i = index; i < nums.size(); i++) {
if (!visited[i]) {
visited[i] = true;
if (helper(nums, i + 1, targetSum, curSum + nums[i], count, visited)) return true;
visited[i] = false;
}
}
return false;
}
};
```
希望这个回答能帮到你!
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![application/x-zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![sb3](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)