题目

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

示例 1：

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

示例 2:

  1. 输入: nums = [1,2,3,4], k = 3
  2. 输出: false


提示：

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

  • 每个元素的频率在 [1,4] 范围内

    解题方法

    递归回溯+剪枝优化

    递归回溯的方式遍历每个元素的全部分配情况，并对分配情况进行剪枝优化执行效率。创建k个子集，剪枝策略如下：

    • 第1个元素只能够放入到第一个子集中，不用考虑放入到其他子集的情况。
    • 如果当前元素加当前子集的和超过数组和的均值时，跳过当前子集。
    • 如果当前子集与上一个子集和一致，则跳过当前子集。

时间复杂度O(k^n)，空间复杂度O(n)
C++代码：

  1. class Solution {
  2. private:
  3.     int average;
  4. public:
  5.     bool dfs(vector<int>& nums, vector<int>& buckets, int idx, int k) {
  6.         if(idx==nums.size()) {
  7.             for(int sum : buckets) {
  8.                 if(sum != average)  return false;
  9.             }
  10.             return true;
  11.         }
  13.         bool result = false;
  14.         for(int i=0; i<k; i++) {
  15.             if(idx==0 && i>0)   break;
  16.             if(buckets[i] + nums[idx] > average)    continue;
  17.             if(i>0 && buckets[i] == buckets[i-1])  continue;
  19.             buckets[i] += nums[idx];
  20.             result = dfs(nums, buckets, idx+1, k);
  21.             buckets[i] -= nums[idx];
  22.             if(result)   break;
  23.         }
  24.         return result;
  25.     }
  27.     bool canPartitionKSubsets(vector<int>& nums, int k) {
  28.         int sum = 0;
  29.         for(int num : nums)     sum+=num;
  30.         if(sum%k)   return false;
  31.         average = sum / k;
  32.         vector<int> buckets(k, 0);
  33.         return dfs(nums, buckets, 0, k);
  34.     }
  35. };

动态规划+状态压缩

使用一个整数表示一个集合（二进制表示中每一位代表数组中对应位的数字是否包含在集合内部）。使用动态数组dp[i]描述集合i能否被分为k个相等的子集。
时间复杂度O(n*k^n)，空间复杂度O(k^n)。
C++代码：

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int len = nums.size();
        if(len<k)   return false;
        int average = 0;
        for(int num : nums)     average += num;
        if(average%k)   return false;
        average /= k;

        int size = (1<<len);
        vector<int> dp(size, -1);
        dp[0] = 0;
        for(int i=1; i<size; i++) {
            for(int j=0; j<len; j++) {
                if( !(i&(1<<j)) )   continue;
                int pre = i & ~(1<<j);
                if(dp[pre]!=-1 && dp[pre]+nums[j]<=average) {
                    dp[i] = (dp[pre]+nums[j])%average;
                    break;
                }
            }
        }
        return dp[size-1]==0;
    }
};