కలయికలు లీట్‌కోడ్ పరిష్కారం


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది Adobe అమెజాన్ ఆపిల్ <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> గూగుల్ మైక్రోసాఫ్ట్ యాహూ
బ్యాక్‌ట్రాకింగ్

కాంబినేషన్ లీట్‌కోడ్ సొల్యూషన్ అనే సమస్య మనకు n మరియు k అనే రెండు పూర్ణాంకాలను అందిస్తుంది. 1 మూలకాల నుండి n మూలకాల నుండి k మూలకాలను ఎంచుకున్న అన్ని శ్రేణులను ఉత్పత్తి చేయమని మాకు చెప్పబడింది. మేము ఈ సన్నివేశాలను ఒకగా తిరిగి ఇస్తాము అమరిక. సమస్యపై మంచి అవగాహన పొందడానికి కొన్ని ఉదాహరణల ద్వారా చూద్దాం.

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

వివరణ: అవుట్పుట్ మొదటి n సహజ సంఖ్యల నుండి k మూలకాలను ఎంచుకునే అన్ని మార్గాలను చూపుతుంది. ఇక్కడ, సంఖ్యల క్రమం పట్టింపు లేదు. సంఖ్యల సేకరణ మాత్రమే ముఖ్యమైనది.

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

వివరణ: ఇక్కడ, మనకు ఒకే మూలకం ఉన్నందున. ఒకే మూలకాన్ని ఎంచుకోమని కూడా మాకు చెప్పబడింది. అందువలన అవుట్పుట్ [[1]].

కాంబినేషన్ లీట్‌కోడ్ సొల్యూషన్ కోసం అప్రోచ్

సమస్య కాంబినేషన్ లీట్‌కోడ్ సొల్యూషన్ మమ్మల్ని మొదటి n సహజ సంఖ్యల నుండి k మూలకాలను ఎంచుకునే అన్ని సన్నివేశాలను రూపొందించమని కోరింది. కాబట్టి, ఇది k మూలకాలను ఎంచుకోవడానికి అందుబాటులో ఉన్న అన్ని nCk కలయికలను ఉత్పత్తి చేస్తుంది. సాధారణంగా, సీక్వెన్సుల తరం పాల్గొన్న పనులు పునరావృతం ఉపయోగించి పరిష్కరించబడతాయి. కాబట్టి, మేము సమస్యకు పునరావృత విధానాన్ని ప్రయత్నిస్తాము. మరియు అటువంటి కలయికలను నిల్వ చేయడానికి ఉద్దేశించిన వెక్టర్ను ట్రాక్ చేయండి.

కాబట్టి, మేము ఖాళీ వెక్టర్‌తో ప్రారంభిస్తాము. మేము దానిలోకి ఒక మూలకాన్ని నెట్టివేస్తాము. మిగిలిన n-1 మూలకాల నుండి k-1 మూలకాలను ఎంచుకునే ఉపప్రాబ్లమ్‌ను పునరావృతంగా పరిష్కరించండి. ఈ విధంగా మేము 0 అంశాలను ఎంచుకునే సమస్యను చేరే వరకు సమస్యను తగ్గించుకుంటాము. ఇది జరిగినప్పుడు, మేము ఈ తాత్కాలిక వెక్టర్‌ను మా సమాధానానికి నెట్టివేస్తాము. చివరికి, ఈ సమాధానం n మూలకాల నుండి k మూలకాలను ఎంచుకునే అన్ని సన్నివేశాలను నిల్వ చేస్తుంది.

కలయికలు లీట్‌కోడ్ పరిష్కారం

కాంబినేషన్ కోసం కోడ్ లీట్‌కోడ్ సొల్యూషన్

సి ++ కోడ్

#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 మూలకాల నుండి k మూలకాలను ఎంచుకునే ద్విపద గుణకం.

అంతరిక్ష సంక్లిష్టత

O (nCk), ఇక్కడ nCk పైన చెప్పినట్లుగా ద్విపద గుణకాన్ని సూచిస్తుంది.