题目描述

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

样例

输入：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

算法

(搜索剪枝) $O(n \log n + \binom{n}{k} (n - k)^k)$

1. 先求出数组的总和，如果总和不是 $k$ 的倍数，则直接返回 false。
2. 求出子集和的目标值，如果数组中有数字大于这个子集和目标值，则返回 false。
3. 将数组 从大到小 排序。贪心地来看，先安排大的数字会更容易先找到答案，这是因为小的数字再后期更加灵活。
4. 我们按照子集去递归填充，即维护一个当前总和 cur，如果当前值等于了目标值，则进行下一个子集的填充。最终，如果只剩下一个子集尚未填充（无需 0 个），则可以直接返回 true。
5. 还需要同时维护一个 last，即表示当前这个子集，需要从数组的哪个位置开始尝试。
6. 这里还有一个非常重要的策略，就是如果当前总和 cur 为 0 时，我们直接指定第一个未被使用的数字作为当前这个子集的第一个数字（最大的数字）。这是防止重复枚举，因为第一个未被使用的数字一定要出现在某个子集中。否则，如果我们最终没有使用这个数字，在尝试下一个集合时，还会重复尝试使用这个数字，造成大量重复计算。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$。
• 首先我们可以确定 $k$ 个子集中最大数字的位置，共有 $O(\binom{n}{k})$ 种选择。
• 剩下每个数字都有 $k$ 种选择，故理论时间复杂度上限为 $O(n \log n + \binom{n}{k} (n - k)^k)$。
• 但实际上的运行时间复杂度远比这个小。

空间复杂度

• 需要额外 $O(n)$ 的空间存储递归的系统栈和记录访问数组。

C++ 代码

class Solution {
public:
    bool solve(int cur, int last, int sum, int r,
               const vector<int> &nums, vector<bool> &used) {

        if (r == 1) return true;
        if (cur > sum) return false;
        if (cur == sum) return solve(0, 0, sum, r - 1, nums, used);

        for (int i = last; i < nums.size(); i++)
            if (!used[i]) {
                used[i] = true;
                if (solve(cur + nums[i], i + 1, sum, r, nums, used))
                    return true;

                used[i] = false;

                // 如果当前正在枚举子集中的第一个数字且失败了，则直接剪枝。
                if (cur == 0) return false;
            }

        return false;
    }

    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int n = nums.size();
        int sum = 0;

        for (int i = 0; i < n; i++)
            sum += nums[i];

        if (sum % k != 0)
            return false;

        sort(nums.rbegin(), nums.rend());

        vector<bool> used(n, false);
        return solve(0, 0, sum / k , k, nums, used);
    }
};