Chương trình kiểm tra phân chia mảng thành k tập con cùng tổng trong C++

Mô tả bài toán

Cho mảng nums và số k. Kiểm tra có thể chia nums thành k tập con không giao nhau mà tổng mỗi tập bằng nhau hay không.

Ví dụ: nums = [4,2,6,5,1,6,3], k=3 → True (các tập [6,3], [6,2,1], [4,5]).

Giải thuật (Backtracking)

1. Tổng tất cả phải chia hết cho k, mỗi tập mục tiêu = sum/k.
2. Dùng DFS thử gán từng số vào một trong k tập, nếu tập nào vượt quá mục tiêu thì cắt tỉa.
3. Sắp xếp nums giảm dần để cắt tỉa sớm.
4. Nếu gán hết tất cả số và tất cả tập đạt mục tiêu → true.

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool check(vector<int>& v) {
        for (int i = 1; i < v.size(); i++)
            if (v[i] != v[0]) return false;
        return true;
    }
    bool dfs(int idx, vector<int>& nums, vector<int>& temp) {
        if (idx == nums.size()) return check(temp);
        for (int i = 0; i < temp.size(); i++) {
            temp[i] += nums[idx];
            if (dfs(idx+1, nums, temp)) return true;
            temp[i] -= nums[idx];
        }
        return false;
    }
    bool solve(vector<int>& nums, int k) {
        vector<int> temp(k);
        return dfs(0, nums, temp);
    }
};

bool solve(vector<int>& nums, int k) {
    return (new Solution())->solve(nums, k);
}

int main() {
    vector<int> v = {4,2,6,5,1,6,3};
    int k = 3;
    cout << solve(v, k);
    return 0;
}

Đầu vào

{4,2,6,5,1,6,3}, 3

Đầu ra

1