image.png

1.题解 回溯 直接100%

  1. class Solution {
  2. public:
  3.     bool canPartitionKSubsets(vector<int>& nums, int k) {
  4.         int ans = accumulate(nums.begin(),nums.end(),0);
  5.         if(ans%k !=0)return false; //排除不可能的结果
  6.         int target = ans/k;
  7.         sort(nums.begin(),nums.end(),greater<int>()); //从大到小的排序，减少循环
  8.         if(*max_element(nums.begin(),nums.end())>target) return false;//如果有大于target的，肯定会报错。
  10.         vector<bool> used(nums.size(),false);
  11.         vector<int> bucket(k,0);
  12.         return dfs(bucket,used,0,0,target,nums);
  13.     }
  15.     bool dfs(vector<int> &bucket,vector<bool> &used,int b,int start,int target,vector<int>& nums) { //start为当前数字位置，b为当前的桶
  16.         if(b == bucket.size()) return true;
  17.         if(bucket[b] == target) return dfs(bucket,used,b+1,0,target,nums);
  19.         for(int i=start;i<nums.size();i++) {
  20.             if(bucket[b] + nums[i] > target) continue;
  21.             if(used[i]) continue;
  22.             used[i] = true;
  23.             bucket[b] += nums[i];
  24.             if(dfs(bucket,used,b,i+1,target,nums)) return true;
  26.             used[i] = false;
  27.             bucket[b] -= nums[i];
  29.             if(bucket[b] == 0) return false; //如果处理之后又bucket还为0，直接剪枝
  30.         }
  31.         return false;
  32.     }
  33. };

2.题解 dp

  1. class Solution {
  2.     int dp[(1 << 16) + 2];
  3. public:
  4.     bool canPartitionKSubsets(vector<int>& nums, int k) {
  5.         int n = nums.size();
  6.         fill(dp,dp+(1<<16)+2,-1);
  7.         int sum = 0;
  8.         for(int i = 0;i < n;i++){
  9.             sum += nums[i];
  10.         }
  11.         if (sum % k != 0) return false;
  12.         int target = sum / k;
  13.         dp[0] = 0;
  14.         for(int mask = 0; mask < (1 << n);mask++){
  15.             if(dp[mask] == -1) continue;
  16.             for(int i = 0;i < n;i++){
  17.                 if(!(mask & (1 << i)) && dp[mask] + nums[i] <= target)
  18.                     dp[mask | (1 << i)] = (dp[mask] + nums[i]) % target; //能否刚好为0
  19.             }
  20.         }
  21.         return dp[(1 << n)-1] == 0; //  所有书取到
  22.     }   
  23. };