संयोजन Leetcode समाधान


कठिनाई स्तर मध्यम
में अक्सर पूछा एडोब वीरांगना सेब Facebook गूगल माइक्रोसॉफ्ट याहू
बैक ट्रैकिंग

समस्या संयोजन Leetcode Solution हमें दो पूर्णांक, n और k प्रदान करता है। हमें उन सभी दृश्यों को उत्पन्न करने के लिए कहा जाता है जिनके तत्वों में 1 से n तक के तत्वों को उठाया गया है। हम इन दृश्यों को एक के रूप में वापस करते हैं सरणी। आइए हम कुछ उदाहरणों के माध्यम से समस्या की बेहतर समझ प्राप्त करें।

n = 4, k = 2
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

स्पष्टीकरण: आउटपुट पहले n प्राकृतिक संख्याओं में से k तत्वों को चुनने के सभी तरीके दिखाता है। यहां, संख्याओं का क्रम कोई मायने नहीं रखता। केवल संख्याओं का संग्रह मायने रखता है।

n = 1, k = 1
[[1]]

स्पष्टीकरण: यहाँ, चूंकि हमारे पास एक ही तत्व है। हमें एक तत्व को चुनने के लिए भी कहा जाता है। इस प्रकार आउटपुट [[१]] है।

संयोजन Leetcode समाधान के लिए दृष्टिकोण

समस्या संयोजन Leetcode Solution ने हमें पहले n प्राकृतिक संख्याओं में से k तत्वों को चुनने के सभी दृश्यों को उत्पन्न करने के लिए कहा। तो, यह केवल k तत्वों को लेने के लिए उपलब्ध सभी nCk संयोजन उत्पन्न कर रहा है। आम तौर पर, अनुक्रम की पीढ़ी को शामिल करने वाले कार्यों को पुनरावृत्ति का उपयोग करके हल किया जाता है। इसलिए, हम समस्या के पुनरावर्ती दृष्टिकोण की कोशिश करते हैं। और एक वेक्टर का ध्यान रखें जो इस तरह के संयोजनों को संग्रहीत करने का लक्ष्य रखता है।

तो, हम एक खाली वेक्टर के साथ शुरू करते हैं। हम इसमें एक तत्व को आगे बढ़ाते हैं। फिर पुन: शेष n-1 तत्वों में से k-1 तत्वों को चुनने का एक उपप्रकार हल करें। इस तरह हम 0 तत्वों को लेने की समस्या तक पहुंचने तक समस्या को कम करते रहते हैं। जब ऐसा होता है, तो हम अपने जवाब के लिए इस अस्थायी वेक्टर को धक्का देते हैं। अंत में, यह उत्तर k तत्वों को n तत्वों से बाहर निकालने के सभी दृश्यों को संग्रहीत करता है।

संयोजन Leetcode समाधान

संयोजन Leetcode समाधान के लिए कोड

C ++ कोड

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

void rec(int i, int k, int n, vector<int>& cur, vector<vector<int>>& res){
    if(cur.size()==k) {
        res.push_back(cur);
    } else {
        for(int j=i;j<=n;j++) {
            cur.push_back(j);
            rec(j+1, k, n, cur, res);
            cur.pop_back();
        }
    }
}

vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> res;
    vector<int> cur;
    rec(1, k, n, cur, res);
    return res;
}

int main(){
    vector<vector<int>> output = combine(4, 2);
    for(auto singleList: output){
        for(auto element: singleList)
            cout<<element<<" ";
        cout<<endl;
    }
}
1 2
1 3
1 4
2 3
2 4
3 4

जावा कोड

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  static List<List<Integer>> res = new ArrayList<List<Integer>>();
  
    public static void rec(int i, int k, int n, ArrayList<Integer> cur){
        if(cur.size()==k) {
            res.add(new ArrayList(cur));
        } else {
            for(int j=i;j<=n;j++) {
                cur.add(j);
                rec(j+1, k, n, cur);
                cur.remove(cur.size()-1);
            }
        }
    }
    
    public static List<List<Integer>> combine(int n, int k) {
        ArrayList<Integer> cur = new ArrayList<Integer>();
        rec(1, k, n, cur);
        return res;
    }

  public static void main (String[] args) throws java.lang.Exception{
    List<List<Integer>> res = combine(4, 2);
    System.out.println(res);
  }
}
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

जटिलता विश्लेषण

समय जटिलता

O (k * nCk), यहाँ nCk का अर्थ है n तत्वों को n तत्वों से बाहर निकालने का द्विपद गुणांक।

अंतरिक्ष जटिलता

O (nCk), जैसा कि nCk के ऊपर बताया गया है, द्विपद गुणांक को संदर्भित करता है।