分区为 K 个相等和的子集

问题陈述

在这个描述中，我们将给出一个整数数组 nums 和一个整数 k，如果可以将这个数组分成 k 个非空子集，并且每个子集的和都相等，则返回 true。

示例 1

输入： nums = [4,3,2,3,5,2,1]，k = 4

说明

• 数组元素的总和为 20，因此每个子集的目标和为 20 / 4 = 5。
• 将数组按降序排序得到 [5, 4, 3, 3, 2, 2, 1]。
• 我们开始回溯过程。
• 我们可以选择 5 并形成一个和为 5 的子集。
• 我们递归地尝试用剩余元素形成剩余的子集，确保每个子集的和都是 5。
• 我们成功地形成了子集 (5)、(4, 1)、(3, 2)、(3, 2)，并返回 true。
• 因此，可以将数组分成 4 个和相等的子集，所以输出为 true。

示例 2

输入： nums = [1,2,3,4]，k = 3

说明

• 数组元素的总和为 10，因此每个子集的目标和为 10 / 3 = 3.33... 由于我们需要整数和，因此不可能将总和平均分配给子集。
• 将数组按降序排序得到 [4, 3, 2, 1]。
• 我们开始回溯过程。
• 我们可以选择 4 并形成一个和为 4 的子集。
• 我们递归地尝试用剩余元素形成剩余的子集，确保每个子集的和都是 4。
• 然而，我们无法使用剩余元素 [1, 2, 3] 形成另外两个和均为 4 的子集，因为它们的和为 1 + 2 + 3 = 6，大于 4。
• 因此，不可能将数组分成 3 个和相等的子集，所以输出为 false。

示例 3

输入： nums=[ 2, 2, 2, 3, 3, 4, 4, 5]，k=4

说明

• 数组元素的总和为 25，因此每个子集的目标和为 25 / 4 = 6.25。由于我们需要整数和，因此不可能将总和平均分配给子集。
• 将数组按降序排序得到 [5, 4, 4, 3, 3, 2, 2, 2]。
• 我们开始回溯过程。
• 我们可以选择 5 并形成一个和为 5 的子集。
• 我们递归地尝试用剩余元素形成剩余的子集，确保每个子集的和都是 5。
• 然而，选择第一个元素后，剩余的和为 25 - 5 = 20，我们需要用这个和形成 3 个子集。由于 20 / 3 = 6.66...，因此不可能将这个和平均分配给具有整数和的子集。
• 因此，不可能将数组分成 4 个和相等的子集，所以输出为 false。

使用回溯的 Java 方法

输出

代码解释

回溯方法

• 此技术使用回溯算法，迭代地查找数组中总和达到目标值的子集。

基本情况： 如果 k == 0，表示所有子集都已找到，因此返回 true。

找到目标子集和： 如果 subsetSum 等于 target，表示找到了目标子集和，它会递归地搜索下一个子集。

递归： 在更新 subsetSum 并将当前元素标记为已访问后，它会对后续元素执行递归搜索。

回溯： 如果当前元素未形成有效子集，它会取消标记该元素并继续下一个元素。

reverse 方法

• 此技术将数组按降序排序，以最大化回溯过程的效率。它还会反转数组元素。

canPartitionKSubsets 方法

• 确定数组是否可以分成 k 个子集的第一步是使用此过程。
• 它确定数组的总和是否能被 k 整除。
• 它确定每个子集的目标总和（target）。
• 为了使回溯过程尽可能高效，数组按降序排序。
• 初始化一个数组来记录已访问的数字。
• 它采用回溯技术来识别总和达到所需金额的子集。
• 如果找到子集，则返回 true；否则，返回 false。

时间复杂度

• CanPartitionKSubsets 的回溯方法具有指数时间复杂度，即 O(2^(k*n))，其中 'k' 是子集的数量，'n' 是输入数组的长度。

空间复杂度

• 空间复杂度为 O(n)，其中 'n' 是输入数组的长度。这是因为布尔数组 'vis' 用于指示在回溯过程中已访问的元素。

使用位掩码的 Java 方法

输出

代码解释

solve 方法

• 此方法中使用的递归回溯技术确定数组是否可以分成 k 个子集。

基本情况

• 如果 k == 0，则返回 true，因为所有项都已处理；如果 mask == 0，则返回 false。
• 如果 k == 0，则返回 true，因为它表示所有子集都已找到。
• 如果已计算结果，则从记忆化数组中取出结果。
• 遍历数组中的项，它确定每个项是否可以是当前子集的一部分。

它递归地探索两种可能性

• 如果当前总和不超过目标，则将当前元素添加到其中。
• 如果达到目标和，则完成当前子集并继续下一个子集。
• 计算结果后，它会更新记忆化数组并返回。

时间复杂度

• 此解决方案的时间复杂度为 O(k. 2^n)，其中 n 是数组的元素计数，k 是子集的数量。

空间复杂度

• 记忆化数组 dp 也是空间复杂度为 O(k.2^n) 的另一个原因。它跟踪子问题的解决方案，每个子问题可能包含 k 行以及与可能的子集组合一样多的列。