原文链接: https://leetcode-cn.com/problems/partition-to-k-equal-sum-subsets

英文原文

Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.

 

Example 1:

Input: nums = [4,3,2,3,5,2,1], k = 4
Output: true
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Example 2:

Input: nums = [1,2,3,4], k = 3
Output: false

 

Constraints:

• 1 <= k <= nums.length <= 16
• 1 <= nums[i] <= 104
• The frequency of each element is in the range [1, 4].

中文题目

给定一个整数数组  nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

示例 1：

输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出： True
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。

 

提示：

• 1 <= k <= len(nums) <= 16
• 0 < nums[i] < 10000

通过代码

官方题解

这道题我们当然可以采用枚举的方式（回溯算法、深度优先遍历）去完成。但是

• 题目只问我们是不是可以划分，没有问我们应该怎样划分；
• 注意到题目给出的数据范围 $1 \le k \le len(nums) \le 16$。

有一定刷题经验的朋友就会知道，这样的问题可以使用「动态规划」去做，并且这是一类使用状态压缩技巧的「动态规划」问题。

方法：动态规划（状态压缩 DP）

动态规划基于这样的想法：

如果一个集合多考虑一个数，恰好使得添加了一个数以后的集合的平均数恰好为 $\cfrac{sum}{k}$。那么添加了一个数以后的集合就是满足条件的输入数组的一个或者若干个子集。

集合是什么样的可以通过枚举，题目给出了数据范围：$1 \le k \le len(nums) \le 16$。因此我们可以用一个整数就可以表示一个集合。

例如，输入数组为 nums = [6, 5, 5, 4]，整数 $3$ 的二进制表示为 $11$（忽略前导 $0$），因此整数 $3$ 表示的集合为 [6, 5]

动态规划的解法从空集合开始，一个数一个数往符合题意的集合里添加元素，每一次只尝试添加一个数。

如果集合里所有元素的和，模（mod） target 加上当前考虑的一个数 num 以后的和小于等于每个划分的平均数 target，那么这个子集有可能是满足题意的一个或者多个划分，否则就一定不是满足题意的一个或者多个划分。

状态压缩 DP 考虑了所有可能出现的情况（请大家通过代码仔细体会）。具体实现细节请见「参考代码」。

参考代码：

[]
class Solution {

    public boolean canPartitionKSubsets(int[] nums, int k) {
        if (k == 1) {
            return true;
        }

        int len = nums.length;
        Arrays.sort(nums);
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % k != 0) {
            return false;
        }
        int target = sum / k;
        if (nums[len - 1] > target) {
            return false;
        }

        int size = 1 << len;
        boolean[] dp = new boolean[size];
        dp[0] = true;
        int[] currentSum = new int[size];
        for (int i = 0; i < size; i++) {
            // 总是基于 dp[i] = true 的前提下进行状态转移
            if (!dp[i]) {
                continue;
            }

            // 基于当前状态，添加一个数以后
            for (int j = 0; j < len; j++) {
                if ((i & (1 << j)) != 0) {
                    continue;
                }
                int next = i | (1 << j);
                if (dp[next]) {
                    continue;
                }
                if ((currentSum[i] % target) + nums[j] <= target) {
                    currentSum[next] = currentSum[i] + nums[j];
                    dp[next] = true;
                } else {
                    // 由于数组已经排好序，如果 (currentSum[i] % target) + nums[j] > target，剩下的数就没有必要枚举
                    break;
                }
            }
        }
        return dp[size - 1];
    }
}

复杂度分析：

• 时间复杂度：$O(N * 2^N)$。其中 $N$ 是输入数组 nums 的长度。有 $2^N$ 个状态，每个状态对 nums 执行 $O(N)$ 次尝试；
• 空间复杂度：$O(2^N)$，状态数组的长度、数组 currentSum 的和。

统计信息

通过次数	提交次数	AC比率
32603	72702	44.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
分割等和子集	中等