कॉम्बिनेशन लीटकोड सोल्यूशन


अडचण पातळी मध्यम
वारंवार विचारले अडोब ऍमेझॉन सफरचंद फेसबुक Google मायक्रोसॉफ्ट याहू
बॅकट्रॅकिंग

समस्या कॉम्बिनेशन लीटकोड सोल्यूशन आम्हाला दोन पूर्णांक एन, आणि के प्रदान करते. आम्हाला असे अनुक्रम तयार करण्यास सांगितले आहे ज्यात 1 घटकांमधून एन घटकांमधून के घटकांनी निवडले आहेत. आम्ही हे अनुक्रम एक म्हणून परत करतो अॅरे. समस्येचे अधिक चांगले ज्ञान मिळविण्यासाठी आपण काही उदाहरणे पाहू या.

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

स्पष्टीकरणः आउटपुट प्रथम एन नैसर्गिक संख्येच्या बाहेर के घटक निवडण्याचे सर्व मार्ग दर्शविते. येथे संख्या क्रमवारी लावण्यात काही फरक पडत नाही. फक्त संख्या संग्रह महत्वाची आहे.

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

स्पष्टीकरणः येथे आपल्यात एकच घटक आहे. आम्हाला एकच घटक निवडण्यास सांगितले जाते. हे आऊटपुट [[1]] आहे.

कॉम्बिनेशन लीटकोड सोल्यूशनसाठी दृष्टीकोन

समस्या कॉम्बिनेशन्स लीटकोड सोल्यूशनने आम्हाला प्रथम एन नैसर्गिक संख्येच्या बाहेर के घटक निवडण्याचे सर्व क्रम तयार करण्यास सांगितले. तर हे के घटकांना निवडण्यासाठी उपलब्ध सर्व एनसीके संयोजन तयार करीत आहे. सामान्यत: अनुक्रम तयार करण्याच्या कामांची पुनरावृत्ती वापरून निराकरण केली जाते. तर, आम्ही समस्येवर पुन्हा पुन्हा विचारण्याचा प्रयत्न करतो. आणि अशा संयोजनांचा संग्रह करण्याच्या उद्देशाने एका वेक्टरचा मागोवा ठेवा.

तर, आम्ही रिक्त वेक्टरपासून प्रारंभ करतो. आम्ही त्यात एक घटक ढकलतो. तर उर्वरित एन -1 घटकांमधून के -1 घटक निवडण्याची उप-समस्या पुन्हा पुन्हा सोडवा. अशाप्रकारे आम्ही 0 घटक निवडण्याच्या समस्येपर्यंत आम्ही समस्या कमी करत राहतो. जेव्हा हे घडते, तेव्हा आम्ही आमच्या उत्तरासाठी या तात्पुरत्या वेक्टरला ढकलतो. शेवटी, हे उत्तर एन घटकांमधून के घटक निवडण्याचे सर्व क्रम संग्रहित करते.

कॉम्बिनेशन लीटकोड सोल्यूशन

कॉम्बिनेशन लीटकोड सोल्यूशनसाठी कोड

सी ++ कोड

#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]]

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (के * एनसीके), येथे एनसीके म्हणजे एन घटकांमधून के घटक निवडण्याचे द्विपद गुणांक.

स्पेस कॉम्प्लेक्सिटी

ओ (एनसीके), एनसीकेने वर सांगितल्याप्रमाणे द्विपदी गुणांक होय.