Partition to K Equal Sum Subsets trong C++

Cho mảng nums và số nguyên dương k. Kiểm tra có thể chia mảng thành k subset không rỗng có tổng bằng nhau hay không.

Ví dụ: nums = [4,3,2,3,5,2,1], k = 4 → true, vì chia được thành [[5], [1,4], [2,3], [2,3]].

Giải thuật (DP trên bitmask)

Tạo mảng dp và total kích thước 2^n.
Sắp xếp nums, tính sum tổng mảng.
Nếu sum % k != 0 hoặc max(nums) > sum/k → false.
dp[0] = true, sum /= k.
Duyệt mask i từ 0 đến 2^n - 1:
- Nếu dp[i] true, thử thêm mỗi phần tử j chưa trong mask:
  - temp = i | (1<.


Trả về dp[(1<.


Ví dụ code
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int n = nums.size();
        vector<bool> dp(1 << n);
        vector<int> total(1 << n);
        sort(nums.begin(), nums.end());
        int sum = 0;
        for (int x : nums) sum += x;
        if (sum % k || nums.back() > sum / k) return false;
        dp[0] = true;
        sum /= k;
        for (int i = 0; i < (1 << n); i++) {
            if (dp[i]) {
                for (int j = 0; j < n; j++) {
                    int temp = i | (1 << j);
                    if (temp != i) {
                        if (nums[j] <= sum - (total[i] % sum)) {
                            dp[temp] = true;
                            total[temp] = total[i] + nums[j];
                        } else break;
                    }
                }
            }
        }
        return dp[(1 << n) - 1];
    }
};

int main() {
    Solution ob;
    vector<int> v = {4,3,2,3,5,2,1};
    cout << ob.canPartitionKSubsets(v, 4);
    return 0;
}
Input
[4,3,2,3,5,2,1] 4
Output
1