0698.cpp (1900B)
1 class Solution { 2 public: 3 bool canPartitionKSubsets(vector<int> &nums, int k) const { 4 int acc = 0; 5 6 for (const int n : nums) 7 acc += n; 8 if (acc % k) return false; 9 10 const int goal = acc / k; 11 12 sort(rbegin(nums), rend(nums)); 13 if (nums[0] > goal) return false; 14 15 const function<bool(uint16_t, int, int, int)> rec = [&](uint16_t visited, int left, int sum, 16 int start) { 17 if (sum == goal) left--, sum = 0, start = 0; 18 if (left == 1) return true; 19 20 for (int i = start; i < size(nums); i++) { 21 const uint16_t mask = 1 << i; 22 if (visited & mask) continue; 23 if (sum + nums[i] > goal) continue; 24 25 if (rec(visited | mask, left, sum + nums[i], i + 1)) return true; 26 if (sum == 0) return false; 27 } 28 29 return false; 30 }; 31 32 return rec(1, k, nums[0], 1); 33 } 34 }; 35 36 class Solution { 37 public: 38 bool canPartitionKSubsets(vector<int> &nums, int k) const { 39 static int acc[16]; 40 int sum = 0; 41 42 for (const int n : nums) 43 sum += n; 44 if (sum % k) return false; 45 46 const int goal = sum / k; 47 48 sort(rbegin(nums), rend(nums)); 49 if (nums[0] > goal) return false; 50 51 memset(acc, 0x00, sizeof(acc)); 52 acc[0] = nums[0]; 53 54 function<bool(int)> rec = [&](int crnt) { 55 if (crnt == size(nums)) return true; 56 57 for (int i = 0; i < k; i++) { 58 if (acc[i] + nums[crnt] > goal) continue; 59 60 acc[i] += nums[crnt]; 61 if (rec(crnt + 1)) return true; 62 acc[i] -= nums[crnt]; 63 64 if (acc[i] == 0) return false; 65 } 66 67 return false; 68 }; 69 70 return rec(1); 71 } 72 };