What is the key pattern to solve Check if it is Possible to Split Array?

The main pattern is state transition dynamic programming combined with greedy selection of valid subarray splits.

Can this problem be solved using pure recursion?

Yes, but pure recursion may be inefficient; DP with greedy choices ensures faster evaluation and avoids repeated computations.

What is a common mistake when implementing DP for this problem?

Ignoring that both resulting arrays must be good when updating DP states often leads to incorrect results.

Does array order affect the solution?

Yes, the split positions depend on the original order since subarrays must preserve sequence to remain good.

Is early termination helpful in this problem?

Absolutely, detecting unsplittable arrays early prevents unnecessary computation and speeds up the solution.

#2811

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

判断是否能拆分数组

给你一个长度为 n 的数组 nums 和一个整数 m 。请你判断能否执行一系列操作，将数组拆分成 n 个非空数组。一个数组被称为好的，如果：子数组的长度为 1 ，或者子数组元素之和大于或等于 m 。在每一步操作中，你可以选择一个长度至少为 2 的现有数组（之前步骤的结果）并将其…

数组动态规划贪心

题目描述

给你一个长度为 n 的数组 nums 和一个整数 m 。请你判断能否执行一系列操作，将数组拆分成 n 个非空数组。

一个数组被称为好的，如果：

子数组的长度为 1 ，或者
子数组元素之和 大于或等于 m 。

在每一步操作中，你可以选择一个 长度至少为 2 的现有数组（之前步骤的结果）并将其拆分成 2 个子数组，而得到的每个子数组都需要是好的。

如果你可以将给定数组拆分成 n 个满足要求的数组，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [2, 2, 1], m = 4

输出：true

解释：

将 [2, 2, 1] 切分为 [2, 2] 和 [1]。数组 [1] 的长度为 1，数组 [2, 2] 的元素之和等于 4 >= m，所以两者都是好的数组。
将 [2, 2] 切分为 [2] 和 [2]。两个数组的长度都是 1，所以都是好的数组。

示例 2：

输入：nums = [2, 1, 3], m = 5

输出：false

解释：

第一步必须是以下之一：

将 [2, 1, 3] 切分为 [2, 1] 和 [3]。数组 [2, 1] 既不是长度为 1，也没有大于或等于 m 的元素和。
将 [2, 1, 3] 切分为 [2] 和 [1, 3]。数组 [1, 3] 既不是长度为 1，也没有大于或等于 m 的元素和。

因此，由于这两个操作都无效（它们没有将数组分成两个好的数组），因此我们无法将 nums 分成 n 个大小为 1 的数组。

示例 3：

输入：nums = [2, 3, 3, 2, 3], m = 6

输出：true

解释：

将 [2, 3, 3, 2, 3] 切分为 [2] 和 [3, 3, 2, 3]。
将 [3, 3, 2, 3] 切分为 [3, 3, 2] 和 [3]。
将 [3, 3, 2] 切分为 [3, 3] 和 [2]。
将 [3, 3] 切分为 [3] 和 [3]。

提示：

1 <= n == nums.length <= 100
1 <= nums[i] <= 100
1 <= m <= 200

lightbulb

解题思路

方法一：记忆化搜索

我们先预处理得到前缀和数组 $s$ ，其中 $s[i]$ 表示数组 $nums$ 的前 $i$ 个元素之和。

接下来，我们设计一个函数 $dfs(i, j)$ ，表示对于数组 $nums$ 的下标范围 $[i, j]$ ，是否存在一种满足条件的拆分方法。如果存在，返回 true，否则返回 false。

函数 $dfs(i, j)$ 的计算过程如下：

如果 $i = j$ ，那么只有一个元素，不需要拆分，返回 true；

否则，我们枚举拆分点 $k$ ，其中 $k \in [i, j]$ ，如果满足以下条件，那么就可以拆分成 $nums[i,.. k]$ 和 $nums[k + 1,.. j]$ 两个子数组：

子数组 $nums[i,..k]$ 只有一个元素，或者子数组 $nums[i,..k]$ 的元素之和大于等于 $m$ ；
子数组 $nums[k + 1,..j]$ 只有一个元素，或者子数组 $nums[k + 1,..j]$ 的元素之和大于等于 $m$ ；
$dfs(i, k)$ 和 $dfs(k + 1, j)$ 都为 true。

为了避免重复计算，我们使用记忆化搜索的方法，用一个二维数组 $f$ 记录所有的 $dfs(i, j)$ 的返回值，其中 $f[i][j]$ 表示 $dfs(i, j)$ 的返回值。

时间复杂度 $O(n^3)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 是数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def canSplitArray(self, nums: List[int], m: int) -> bool:
        @cache
        def dfs(i: int, j: int) -> bool:
            if i == j:
                return True
            for k in range(i, j):
                a = k == i or s[k + 1] - s[i] >= m
                b = k == j - 1 or s[j + 1] - s[k + 1] >= m
                if a and b and dfs(i, k) and dfs(k + 1, j):
                    return True
            return False

        s = list(accumulate(nums, initial=0))
        return dfs(0, len(nums) - 1)

speed

复杂度分析

指标	值
时间	complexity depends on iterating through all possible split positions for each subarray, potentially O(n^2) in the worst case. Space complexity is O(n) to store the DP states for subarray validation.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
You might ask how to represent subarray validity efficiently for state transitions.
question_mark
Expect a discussion on when greedy choices simplify DP state decisions.
question_mark
Interviewers may probe whether early termination improves performance on unsplittable arrays.

warning

常见陷阱

外企场景

error
Failing to check that both resulting arrays are good before updating DP states.
error
Assuming any split is valid without considering the problem's good array definition.
error
Overcomplicating with unnecessary recursion instead of leveraging DP and greedy observations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Instead of splitting into size-one arrays, determine if array can be split into subarrays summing to exactly m.
arrow_right_alt
Allow splits only at positions where the sum of elements is even and validate good array recursively.
arrow_right_alt
Change the definition of a good array to require at least one element greater than a threshold in each subarray.

help

常见问题

外企场景

继续练习

#2900 最长相邻不相等子序列 I #2708 一个小组的最大实力值 #2673 使二叉树所有路径值相等的最小代价