LeetCode_problems_solution/source-code/Partition_to_K_Equal_Sum_Subsets.cpp at master · Miscellaneous-Repos-Programming/LeetCode_problems_solution · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    int canPartitionKSubsets(vector<int>& nums, int curr, const int target, int k, int mask, unordered_map<int, unordered_map<int, unordered_map<int, int>>>& dp) {
        if(curr == target) {
            curr = 0;
            k--;
        }
        int n = (int)nums.size();
        if(k == 0 and mask == (1 << n) - 1 and curr == 0) {
            return 1;
        }

        if(dp[k][mask][curr]) {
            return dp[k][mask][curr];
        }

        for(int i = 0; i < n; i++) {
            if(!(mask & (1 << i))) {
                if(curr + nums[i] <= target) {
                    if(canPartitionKSubsets(nums, curr + nums[i], target, k, mask | (1 << i), dp) == 1) {
                        return dp[k][mask][curr] = 1;
                    }
                }
            }
        }
        return dp[k][mask][curr] = 2;
    }
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int n = (int)nums.size();
        int sum = 0;
        for(int val : nums) {
            sum += val;
        }
        if(k == 1) { return true; }
        if(sum % k != 0) {
            return false;
        }
        int target = sum / k;
        int mask = 0;
        unordered_map<int, unordered_map<int, unordered_map<int, int>>> dp;
        return canPartitionKSubsets(nums, 0, target, k, mask, dp) == 1;
    }
};