LeetCode 题解工作台
划分为k个相等的子集
给定一个整数数组 nums 和一个正整数 k ，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。 示例 1： 输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4 输出： True 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于…
6
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
根据题意，我们需要将数组 划分为 个子集，且每个子集的和相等。因此，先累加 中所有元素的和，如果不能被 整除，说明无法划分为 个子集，提前返回 。 如果能被 整除，不妨将每个子集期望的和记为 ，然后创建一个长度为 的数组 ，表示当前每个子集的和。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
示例 1：
输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4 输出： True 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
示例 2:
输入: nums = [1,2,3,4], k = 3 输出: false
提示：
1 <= k <= len(nums) <= 160 < nums[i] < 10000- 每个元素的频率在
[1,4]范围内
解题思路
方法一：DFS + 剪枝
根据题意，我们需要将数组 划分为 个子集，且每个子集的和相等。因此，先累加 中所有元素的和，如果不能被 整除，说明无法划分为 个子集，提前返回 。
如果能被 整除，不妨将每个子集期望的和记为 ，然后创建一个长度为 的数组 ，表示当前每个子集的和。
对数组 进行降序排序（减少搜索次数），然后从第一个元素开始，依次尝试将其加入到 的每个子集中。这里如果将 加入某个子集 后，子集的和超过 ，说明无法放入，可以直接跳过；另外，如果 与 相等，意味着我们在 的时候已经完成了搜索，也可以跳过当前的搜索。
如果能将所有元素都加入到 中，说明可以划分为 个子集，返回 。
class Solution:
def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
def dfs(i):
if i == len(nums):
return True
for j in range(k):
if j and cur[j] == cur[j - 1]:
continue
cur[j] += nums[i]
if cur[j] <= s and dfs(i + 1):
return True
cur[j] -= nums[i]
return False
s, mod = divmod(sum(nums), k)
if mod:
return False
cur = [0] * k
nums.sort(reverse=True)
return dfs(0)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(k * 2^n) in the worst case using bitmask DP, since each subset assignment can produce 2^n states. Space complexity is O(2^n) for memoization. Backtracking alone may approach O(k^n) without pruning, but DP reduces repeated computation. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate recognizes need to calculate target sum and checks divisibility early.
- question_mark
Candidate uses bitmask or memoization to avoid recomputation during subset assignments.
- question_mark
Candidate applies pruning to avoid exploring invalid paths exceeding the target sum.
常见陷阱
外企场景- error
Not checking total sum divisibility by k before recursion, leading to wasted computation.
- error
Failing to track used elements correctly, causing duplicate element usage across subsets.
- error
Skipping memoization or DP optimization, resulting in exponential runtime that times out for n > 12.
进阶变体
外企场景- arrow_right_alt
Partition into 2 equal sum subsets only (simpler case with k=2).
- arrow_right_alt
Allow negative numbers, requiring sum balancing and careful DP states.
- arrow_right_alt
Count the number of distinct k-partitions with equal sum instead of returning boolean.