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

一、题目描述

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

提示：

• 1 <= k <= len(nums) <= 16
• 0 < nums[i] < 10000
• 每个元素的频率在 [1,4] 范围内

二、解题思路

查找所有可能情况，可以采用回溯法。

回溯为了加快速度，还要加上快速剪枝和记忆搜索。

快速剪枝：

• 对数组进行排序，可以方便判断元素的前后大小
• 快速剪枝，只要当前 sum + nums[i] > target，那么后面就不必遍历了

记忆搜索（状态去重）：

数组有 n 位数，所有总共有 2 ^ n 中不同的状态，但是题目限制了 1 < n < 16。

• 可以采用状态压缩的方式，用整数的低 16 位保存 n 位状态
• 压缩状态到整数表示以后，就能用数组 new boolean[1 << n] 进行状态去重

总的处理过程如下：

1. 验证数组总和，是否可以均分成 k 组 sum(nums) % k
2. 验证均值 sum(nums) / k 的有效性，即判断它是否不小于数组所有值
3. 状态压缩，回溯遍历所有情况
4. 回溯过程中，快速剪枝 + 记忆去重

三、复杂度分析

3.1 时间 O(n * 2^n)

总共 2^n 种状态，每种状态进行 n 轮判断，验证可能性。

3.2 空间 O(2^n)

记忆搜索需要 2^n 空间保存所有状态。

四、参考代码

// 搜索数组
int[] nums;
// 状态缓存
boolean[] cache;
// 目标值
int target = 0;

/**
 * 思路：状态压缩 + 记忆搜索
 * <p>
 * 复杂度：O(n * 2^n) 空间 O(2^n)
 * <p>
 * 执行耗时:17 ms,击败了67.38% 的Java用户
 * 内存消耗:40.9 MB,击败了30.37% 的Java用户
 */
private boolean canPartitionKSubsets(int[] nums, int k) {
    // 判断总和够不够均分
    int sum = Arrays.stream(nums).sum();
    if (sum % k != 0) {
        return false;
    }

    // 平均值
    int avg = sum / k;

    // 排序，方便剪枝
    Arrays.sort(nums);

    // 最大值比平均值大，不可能均分
    int n = nums.length;
    if (avg < nums[n - 1]) {
        return false;
    }

    // 状态压缩，用 n 位 1 表示
    int state = (1 << n) - 1;
    this.nums = nums;
    this.target = avg;
    this.cache = new boolean[state + 1];
    Arrays.fill(this.cache, true);

    return dfs(state, 0);
}

/**
 * 递归遍历
 *
 * @param state 状态
 * @param sum   总和
 * @return true/false
 */
private boolean dfs(int state, int sum) {
    // 分配成功
    if (state == 0) {
        return true;
    }
    // 记忆状态去重
    if (!cache[state]) {
        return false;
    }

    int n = nums.length;
    for (int i = 0; i < n; i++) {
        // num[i] 已被使用
        boolean used = ((state >> i) & 1) == 0;
        if (used) {
            continue;
        }
        // 快速剪枝，排序了后面的比前面大
        if (nums[i] + sum > target) {
            break;
        }

        // 设置第 i 位为 0，标记 num[i] 已被使用
        int nextState = state ^ (1 << i);
        // 加够一个 target 后，重新从 0 开始
        int nextSum = (sum + nums[i]) % target;

        // 递归，验证下一个状态是否可行
        if (dfs(nextState, nextSum)) {
            return true;
        }
    }

    // 状态记忆存储
    cache[state] = false;
    return false;
}