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

C++ में सरणी के सभी विशिष्ट सबसेट (या सबसीक्वेंस) योग ढूंढना

मान लीजिए हमारे पास पूर्णांकों का एक सेट है। विशिष्ट योग ढूंढें जो दिए गए सेट के सबसेट से बनाए जा सकते हैं और उन्हें आरोही क्रम में प्रिंट करें। सरणी तत्वों का योग छोटा है। उदाहरण: सरणी [1, 2, 3] के लिए आउटपुट 0, 1, 2, 3, 4, 5, 6 होगा। विशिष्ट सबसेट हैं {}, {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}, जिनके योग मान 0, 1, 2, 3, 3, 5, 4, 6 हैं।

इसे हल करने के लिए, हम डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे। जब दिए गए तत्वों का योग छोटा हो, तो हम एक DP टेबल बना सकते हैं जिसमें पंक्तियों में सरणी का आकार और कॉलम में सरणी के सभी तत्वों का योग होगा।

C++ उदाहरण

#include <iostream>
#include <cstring>
using namespace std;

void displaySubsetSum(int arr[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
    
    bool table[n+1][sum+1];
    memset(table, 0, sizeof(table));
    
    for (int i = 0; i <= n; i++)
        table[i][0] = true;
    
    for (int i = 1; i <= n; i++) {
        table[i][arr[i-1]] = true;
        for (int j = 1; j <= sum; j++) {
            if (table[i-1][j] == true) {
                table[i][j] = true;
                if (j + arr[i-1] <= sum)
                    table[i][j + arr[i-1]] = true;
            }
        }
    }
    
    for (int j = 0; j <= sum; j++)
        if (table[n][j] == true)
            cout << j << " ";
}

int main() {
    int arr[] = {1, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    displaySubsetSum(arr, n);
    return 0;
}

आउटपुट

0 1 2 3 4 5 6
  1. - ऐरे में गैर-दोहराए गए (अलग) तत्वों का योग खोजें C++ में

    मान लीजिए हमारे पास कुछ तत्वों के साथ एक ऐरे A है। हमें ऐरे में सभी अलग-अलग तत्वों का योग खोजना है। तो यदि A = [5, 12, 63, 5, 33, 47, 12, 63], तो अलग-अलग तत्वों का योग 160 है। डुप्लीकेट तत्वों को एक बार मानने के बाद बस अनदेखा कर दिया जाता है। हम इस समस्या को कुशलता से हल करने के लिए अनऑर्डर्ड सेट का

  1. - C++ में सरणी में उन सभी जोड़े (a,b) और (c,d) को खोजें जो ab = cd को संतुष्ट करते हैं

    मान लीजिए हमारे पास एक सरणी A है, उस सरणी से हमें दो जोड़े (a, b) और (c, d) चुनने हैं, जैसे कि ab = cd। मान लीजिए सरणी A = [3, 4, 7, 1, 2, 9, 8]। आउटपुट जोड़े हैं (4, 2) और (1, 8)। इसे हल करने के लिए, हम इन चरणों का पालन करेंगे: i := 0 से n-1 तक, करें j := i + 1 से n-1 तक, करें product = arr[i]

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

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