C++ में k-भागों में समान योग के साथ सूची विभाजन की जांच करने का प्रोग्राम

समस्या विवरण

मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची और एक मान k है, हमें जांचना है कि क्या nums को k अलग-अलग सबसेट में विभाजित करना संभव है जहां प्रत्येक सबसेट का योग समान हो।

उदाहरण के लिए, यदि इनपुट है nums = [4, 2, 6, 5, 1, 6, 3] k = 3, तो आउटपुट True होगा, क्योंकि हम उन्हें इस तरह विभाजित कर सकते हैं: [6, 3], [6, 2, 1], और [4, 5]।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए हम बैकट्रैकिंग का उपयोग करेंगे:

1. एक फंक्शन check() परिभाषित करें जो एक ऐरे v लेता है
   • i := 1 से v के आकार तक: यदि v[i] != v[0], तो false वापस करें
   • true वापस करें
2. एक फंक्शन dfs() परिभाषित करें जो idx, nums ऐरे, temp ऐरे लेता है
   • यदि idx == nums का आकार, तो check(temp) वापस करें
   • ret := false
   • i := 0 से temp के आकार तक:
     • temp[i] := temp[i] + nums[idx]
     • ret := dfs(idx+1, nums, temp)
     • यदि ret true है, तो true वापस करें
     • temp[i] := temp[i] - nums[idx]
   • false वापस करें
3. मुख्य विधि से:
   • आकार k का एक ऐरे temp परिभाषित करें
   • dfs(0, nums, temp) वापस करें

उदाहरण

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

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, 3);
}

इनपुट

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

आउटपुट

1