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


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

समस्या संयोजन Leetcode समाधान हामीलाई दुई पूर्णांक, n, र k प्रदान गर्दछ। हामीलाई सबै अनुक्रमहरू उत्पन्न गर्न भनिएको छ कि के तत्वहरूले एन तत्वहरू १ देखि n लाई खिचेका छन्। हामी यी क्रमहरूलाई ए को रूपमा फर्काउँछौं array। हामी समस्याहरूको राम्रोसँग बुझ्न केही उदाहरणहरू पार गरौं।

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

स्पष्टीकरण: आउटपुटले पहिलो एन प्राकृतिक संख्याहरूको बाहिर के तत्वहरू लिने सबै तरिकाहरू देखाउँदछ। यहाँ, संख्या को क्रम मा फरक पर्दैन। संख्याको स Only्ग्रहको मात्र महत्त्व छ।

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

स्पष्टीकरण: यहाँ, हामीसँग एकल तत्व छन्। हामीलाई एकल तत्व छान्न पनि भनिएको छ। यसरी आउटपुट [[१]] हो।

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

समस्या संयोजन Leetcode समाधान हामीलाई केवल पहिलो एन प्राकृतिक संख्या को बाहिर K तत्वहरु लाई उठाउने सबै अनुक्रम उत्पन्न गर्न सोधे। त्यसो भए, यसले के ई तत्वहरू छनौट गर्नका लागि उपलब्ध सबै एनसीके संयोजनहरू मात्र उत्पन्न गर्दछ। सामान्यतया, अनुक्रमहरूको पुस्तासँग सम्बन्धित कार्यहरू रिकर्सन प्रयोग गरेर समाधान गरिन्छ। त्यसोभए, हामी समस्याको लागि रिकर्सिभ दृष्टिकोण प्रयास गर्दछौं। र भेक्टरको ट्र्याक राख्नुहोस् जुन यस्तो संयोजनहरू भण्डारण गर्ने लक्ष्य राख्दछ।

त्यसो भए, हामी खाली भेक्टरबाट सुरु गर्छौं। हामी यसमा एक तत्व धकेल्छौं। त्यसोभए पुनरावृत्तिक रूपमा के -१ तत्त्वहरू बाँकी एन-१ तत्त्वहरूबाट बाहिर लिने उप-समस्या समाधान गर्नुहोस्। यस तरिकामा हामी समस्या कम गर्न जारी राख्छौं हामी 1 तत्वहरू लिने समस्यामा नपुगुञ्जेल। जब यो हुन्छ, हामी यस अस्थायी भेक्टरलाई हाम्रो उत्तरमा धकेल्छौं। अन्त्यमा, यस उत्तरले n तत्वहरूको बाहिर K तत्वहरू लिने सबै अनुक्रमहरू भण्डार गर्दछ।

संयोजन 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), यहाँ एन सी के भन्नाले n एलिमेन्ट्स बाहिर k एलिमेन्ट लिनुको द्विपक्षीय गुणांक हो।

ठाउँ जटिलता

O (nCk), यहाँ माथि भनिए अनुसार NCk ले द्विपदीय गुणांकलाई जनाउँछ।