LeetCode 698. 划分为k个相等的子集 题目描述 给定一个整数数组 nums 和一个正整数 k ，请判断是否可能将这个数组划分为 k 个非空子集，使得每个子集的所有元素和相等。数组中的元素可能包含重复元素。例如： 输入： nums = [4, 3, 2, 3, 5, 2, 1] , k = 4 输出： true 解释：数组可以划分为 [5] 、 [1,4] 、 [2,3] 、 [2,3] ，每个子集的和均为 5。 解题思路 问题分析 ： 若数组总和无法被 k 整除，直接返回 false 。 每个子集的目标和 target = sum(nums) / k 。 问题转化为：能否将数组元素放入 k 个桶中，使每个桶的和恰好为 target 。 关键难点 ： 元素顺序不影响分组，但直接枚举所有组合会超时（指数级复杂度）。 需要剪枝优化：优先处理大元素（排序降序）、跳过重复元素、失败时回溯。 算法选择 ：回溯 + 剪枝（DFS）。 从第一个桶开始，尝试放入未被使用的元素，若桶和达到 target 则递归处理下一个桶。 若当前桶无法填满，回溯并尝试其他元素。 逐步解题过程 预处理 ： 计算 target ，若不能整除则返回 false 。 将数组降序排序（优先处理大元素，减少分支）。 回溯函数设计 ： 参数：当前桶索引 bucketIndex 、当前桶已装和 currentSum 、已使用元素标记数组 used 。 基线条件：所有桶都填满时（ bucketIndex == k ）返回 true 。 若当前桶和等于 target ，递归处理下一个桶（从索引 0 重新开始选元素）。 遍历未使用元素，尝试加入当前桶： 若 currentSum + nums[i] > target ，跳过。 若前一个相同值元素未被使用，跳过当前重复元素（剪枝）。 标记元素为已使用，递归搜索，若成功则返回 true ，否则回溯。 示例演示 （ nums = [4,3,2,3,5,2,1] , k=4 ）： 总和为 20， target=5 。排序后为 [5,4,3,3,2,2,1] 。 桶1：选 5 → 已满，递归桶2。 桶2：选 4 → 需补 1，选 1 → 已满，递归桶3。 桶3：选 3 → 需补 2，选 2 → 已满，递归桶4。 桶4：剩余 [3,2] ，选 3 → 需补 2，选 2 → 成功。 复杂度分析 最坏时间复杂度：$O(k \cdot 2^n)$（每个元素有 k 个桶可选，但剪枝大幅优化实际运行）。 空间复杂度：$O(n)$（递归栈和标记数组）。 通过回溯与剪枝结合，有效解决了NP难问题的高复杂度挑战。