【状压dp】698.划分为k个相等的子集

Problem: 698. 划分为k个相等的子集

这题没有成功做出来，这里记录对于官解的理解。

思路

第一个重要的点是把题目的要求进行转换。将数组里的元素分为k个和相同的集合，那么对于整个数组的和all这k个集合每一个的和都为all/k，记为per。

起初没有注意到这一点，因此想不出什么思路。

因此，题目就转化为了我们可以逐渐选择元素，在这过程中计算当前累计和curSum，当累计和可以整除per时，证明我们成功选好了一个集合。如果加上当前元素后累计和大于per，证明这个选择是不成立的。

于是，我们需要枚举所有可能的组合情况，以查明数组是否可分。由于每个元素都有选择和不选择两种状态，我们可以使用状压dp来进行记忆化搜索。

状压 DP 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。

状压dp的思想有点类似于哈希，同样把一种状态压缩成了一个整数，并存储在数组中。

在本题中，dp[i]若为true，则表示对于i这种状态，分好的集合中每个集合的内部和都小于等于per。若dp[(i<<n)-1]为true，则表示全部选好时每个集合的内部和都小于等于per，那么这样就分好了集合。

在状态转化时，我们对每个为true的dp[i]逐渐加上若干个元素，记为状态next。若next仍然满足定义，则把dp[next]的值置为true。

理解

最重要的一步就是把题目的要求进行转化，往便于算法处理的方向靠。状压dp对于要遍历若干元素选或不选的情况时很有用。

复杂度

• 时间复杂度: $O(n×2^n)$，其中 n 为数组 nums 的长度，共有 2n 个状态，每一个状态进行了 n 次尝试。
• 空间复杂度: $O(2^n)$，其中 n 为数组 nums 的长度，主要为状态数组的空间开销。

Code

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int all = Arrays.stream(nums).sum();
        if (all % k != 0) {
            return false;
        }
        int per = all / k;
        Arrays.sort(nums);
        int n = nums.length;
        if (nums[n - 1] > per) {
            return false;
        }
        boolean[] dp = new boolean[1 << n];
        int[] curSum = new int[1 << n];
        dp[0] = true;
        for (int i = 0; i < 1 << n; i++) {
            if (!dp[i]) {
                continue;
            }
            for (int j = 0; j < n; j++) {
                if (curSum[i] + nums[j] > per) {
                    break;
                }
                if (((i >> j) & 1) == 0) {
                    int next = i | (1 << j);
                    if (!dp[next]) {
                        curSum[next] = (curSum[i] + nums[j]) % per;
                        dp[next] = true;
                    }
                }
            }
        }
        return dp[(1 << n) - 1];
    }
}