给你一个数组,问你是否能将数组分成 4 等份,即每一份的数字总和都相等,你不能拆分数组中的数字,如果能得到有效划分就返回 true,否则返回 false。
时间: 2023-11-27 16:04:30 浏览: 119
algoboy101#note_blog_leetcode#[548]将数组分割成和相等的子数组1
好的,这是一个比较典型的分组问题,可以使用回溯算法来解决。具体做法如下:
1.首先计算出数组中所有数字的总和 sum,如果 sum 不是 4 的倍数,那么直接返回 false。
2.定义一个数组 groupSum,用来记录每一组累计的数字总和,初始化为 0。
3.对数组进行回溯搜索,每次搜索时从数组开头开始,依次将数字添加到 groupSum 中,如果当前 groupSum[i] 大于 sum/4,那么直接返回 false。
4.如果搜索到第四组时,所有数字都已经被分组,那么就说明可以成功划分,返回 true。
下面是代码实现:
```python
def canPartition(nums):
def dfs(nums, index, groupSum):
if index == len(nums):
return True
for i in range(4):
if groupSum[i] + nums[index] > target:
continue
groupSum[i] += nums[index]
if dfs(nums, index + 1, groupSum):
return True
groupSum[i] -= nums[index]
return False
sum_num = sum(nums)
if sum_num % 4 != 0:
return False
target = sum_num // 4
nums.sort(reverse=True)
if nums[0] > target:
return False
groupSum = [0] * 4
return dfs(nums, 0, groupSum)
```
以上代码中,dfs 函数用来进行回溯搜索,index 表示当前搜索到的数字下标,groupSum 表示当前已经分配的数字总和,如果能成功分配,则返回 True,否则返回 False。
主函数中先计算出数组总和 sum_num,如果 sum_num 不是 4 的倍数,那么直接返回 False,否则将 sum_num // 4 赋值给 target,表示每一组数字总和的目标值。将数组按从大到小的顺序排序,如果最大值大于 target,那么也直接返回 False。最后调用 dfs 函数进行回溯搜索,返回搜索结果即可。
希望能帮到你!
阅读全文