leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

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 };