1013.将数组分成和相等的三个部分

链接：1013.将数组分成和相等的三个部分
难度：Easy
标签：贪心、数组
简介：给你一个整数数组 arr，只有可以将其划分为三个和相等的 非空 部分时才返回 true，否则返回 false。

题解 1 - python

• 编辑时间：2023-01-21
• 执行用时：248ms
• 内存消耗：26.3MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
def canThreePartsEqualSum(self, arr: List[int]) -> bool:
    print(arr)
    n = len(arr)
    nsum = sum(arr)
    print(nsum)
    if nsum / 3 != nsum // 3:
        return False
    num = nsum // 3
    f: bool = False
    def dfs(i: int, frag: int):
        nonlocal f
        if i == n:
            if frag == 3:
                f = True
            return
        vsum = 0
        for i in range(i, n):
            vsum += arr[i]
            if vsum == num:
                dfs(i + 1, frag + 1)
    dfs(0, 0)
    return f