সি++-এ লিস্টকে k-পার্টিশনে ভাগ করা যায় কিনা যাচাই করা (সমান যোগফল)

সমস্যা বিবরণ

একটি সংখ্যার তালিকা nums এবং মান k দেওয়া আছে। চেক করতে হবে nums কে kটি সাবসেটে ভাগ করা যায় কিনা যাতে সব সাবসেটের যোগফল সমান হয়।

উদাহরণ: nums = [4,2,6,5,1,6,3], k = 3 → আউটপুট True। পার্টিশন: [6,3], [6,2,1], [4,5] (সব যোগফল ৯)।

সমাধানের পদ্ধতি

ব্যাকট্র্যাকিং (DFS):

1. মোট যোগফল k দিয়ে বিভাজ্য কিনা চেক করুন।
2. temp[k] অ্যারে রেখে প্রতিটি সাবসেটের করেন্ট যোগফল ট্র্যাক করুন।
3. প্রতিটি উপাদান nums[idx] কে kটি সাবসেটের যেকোনো একটিতে বসানোর চেষ্টা করুন (DFS)।
4. যদি সব উপাদান বসানো যায় এবং সব সাবসেটের যোগফল সমান হয় → true।
5. প্রুনিং: বড় উপাদানগুলো আগে বসান, ডুপ্লিকেট সাবসেট এড়ান।

উদাহরণ কোড

#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);
        bool ret = false;
        for (int i = 0; i < temp.size(); i++) {
            temp[i] += nums[idx];
            ret = dfs(idx+1, nums, temp);
            if (ret) return true;
            temp[i] -= nums[idx];
        }
        return false;
    }
    bool solve(vector<int>& nums, int k) {
        vector<int> temp(k);
        return dfs(0, nums, temp);
    }
};

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

ইনপুট ও আউটপুট

ইনপুট: {4, 2, 6, 5, 1, 6, 3}, 3

আউটপুট: 1