Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में संयोजन योग II (Combination Sum II)


मान लीजिए हमारे पास उम्मीदवार संख्याओं का एक समूह है (सभी तत्व अद्वितीय हैं) और एक लक्ष्य संख्या। हमें उम्मीदवारों में उन सभी अद्वितीय संयोजनों को ढूंढना है जहां उम्मीदवार संख्याओं का योग दिए गए लक्ष्य के बराबर हो। वही संख्या उम्मीदवारों से एक से अधिक बार नहीं चुनी जाएगी। यदि तत्व [2,3,6,7,8] हैं और लक्ष्य मान 8 है, तो संभावित आउटपुट [[2,6],[8]] होगा।

आइए चरण देखें:

  • हम इसे रिकर्सिव तरीके से हल करेंगे। रिकर्सिव फंक्शन का नाम solve() है। यह इंडेक्स, एक सरणी a, पूर्णांक b और दूसरी सरणी temp लेता है। solve मेथड इस तरह काम करेगा:
    • res नामक खाली सरणी परिभाषित करें
    • यदि b = 0, तो temp को res में डालें, और वापस करें
    • यदि इंडेक्स = a का आकार, तो वापस करें
    • यदि b < 0, तो वापस करें
    • सरणी a को सॉर्ट करें
    • i को इंडेक्स से a के आकार – 1 तक की रेंज में:
      • यदि i > इंडेक्स और a[i] = a[i – 1], तो कंटिन्यू करें
      • a[i] को temp में डालें
      • solve(i + 1, a, b – a[i], temp)
      • temp से अंतिम तत्व हटाएं
  • solve() मेथड को इंडेक्स = 0, सरणी a, लक्ष्य b, और दूसरी सरणी temp पास करके कॉल करें
  • res वापस करें

उदाहरण

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

void print_vector(vector<vector<int> > v){
    cout << "[";
    for(int i = 0; i < v.size(); i++){
        cout << "[";
        for(int j = 0; j < v[i].size(); j++){
            cout << v[i][j] << ", ";
        }
        cout << "],";
    }
    cout << "]" << endl;
}

class Solution {
public:
    vector < vector <int> > res;
    void solve(int idx, vector <int> &a, int b, vector <int> temp){
        if(b == 0){
            res.push_back(temp);
            return;
        }
        if(idx == a.size()) return;
        if(b < 0) return;
        sort(a.begin(), a.end());
        for(int i = idx; i < a.size(); i++){
            if(i > idx && a[i] == a[i-1]) continue;
            temp.push_back(a[i]);
            solve(i + 1, a, b - a[i], temp);
            temp.pop_back();
        }
    }
    vector<vector<int> > combinationSum2(vector<int> &a, int b) {
        res.clear();
        vector <int> temp;
        solve(0, a, b, temp);
        return res;
    }
};

int main(){
    Solution ob;
    vector<int> v = {2,3,6,7,8};
    print_vector(ob.combinationSum2(v, 10));
}

इनपुट

[2,3,6,7,8] 8

आउटपुट

[[2, 8, ],[3, 7, ],]
  1. - C++ में रेंज सम क्वेरी - अपरिवर्तनीय

    मान लीजिए हमारे पास पूर्णांकों का एक ऐरे है। हमें इंडेक्स i से j तक मौजूद तत्वों का योग ढूंढना है। दो बातें ध्यान में रखनी हैं कि ऐरे अपरिवर्तनीय होगा, इसलिए तत्व बदले नहीं जाएंगे, और ऐसी कई क्वेरी होंगी। इसलिए हमें बड़ी संख्या में क्वेरी के लिए निष्पादन समय का ध्यान रखना होगा। मान लीजिए ऐरे A = [5

  1. - C++ में सम ऐरे पजल (बिना घटाव ऑपरेटर के)

    यहां हम ऐरे से संबंधित एक रोचक समस्या देखेंगे। n तत्वों वाला एक ऐरे है। हमें n तत्वों का एक और ऐरे बनाना है। लेकिन दूसरे ऐरे का i-th स्थान पहले ऐरे के i-th तत्व को छोड़कर सभी तत्वों का योग रखेगा। और एक प्रतिबंध है कि हम इस समस्या में घटाव ऑपरेटर का उपयोग नहीं कर सकते। यदि हम घटाव ऑपरेशन का उपयोग कर

  1. - C++ में कॉम्बिनेशन्स

    मान लीजिए हमारे पास दो पूर्णांक n और k हैं। हमें 1 ... n में से k संख्याओं के सभी संभावित संयोजन ढूंढने हैं। इसलिए यदि n = 4 और k = 2, तो संयोजन [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] होंगे।इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -हम इसे हल करने के लिए पुनरावर्ती फ़ंक्शन का उपयोग करेंगे। solve