சேர்க்கைகள் லீட்கோட் தீர்வு


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அடோப் அமேசான் ஆப்பிள் பேஸ்புக் கூகிள் மைக்ரோசாப்ட் யாகூ
பின்வாங்கல்

சிக்கல் சேர்க்கைகள் லீட்கோட் தீர்வு எங்களுக்கு இரண்டு முழு எண்களை வழங்குகிறது, n, மற்றும் k. 1 முதல் n வரையிலான 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 கூறுகளைத் தேர்ந்தெடுப்பதற்கான அனைத்து வரிசைகளையும் உருவாக்கும்படி கேட்டது. எனவே, இது கே உறுப்புகளைத் தேர்ந்தெடுப்பதற்கு கிடைக்கக்கூடிய அனைத்து என்.சி.கே சேர்க்கைகளையும் உருவாக்குகிறது. பொதுவாக, வரிசைகளின் தலைமுறை சம்பந்தப்பட்ட பணிகள் மறுநிகழ்வைப் பயன்படுத்தி தீர்க்கப்படுகின்றன. எனவே, சிக்கலுக்கு ஒரு சுழல்நிலை அணுகுமுறையை முயற்சிக்கிறோம். அத்தகைய சேர்க்கைகளை சேமிப்பதை நோக்கமாகக் கொண்ட ஒரு திசையனைக் கண்காணிக்கவும்.

எனவே, வெற்று திசையனுடன் தொடங்குவோம். நாம் ஒரு உறுப்பை அதில் தள்ளுகிறோம். மீதமுள்ள 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 க்கு மேலே கூறியது இருவகை குணகத்தைக் குறிக்கிறது.