සංයෝජන ලීට්කෝඩ් විසඳුම


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇෙබෝ ඇමේසන් Apple ජංගම දුරකථන ෆේස්බුක් ගූගල් මයික්රොසොෆ්ට් යාහූ
පසුගාමී වීම

ගැටළුව සංයෝජන ලීට්කෝඩ් විසඳුම අපට පූර්ණ සංඛ්‍යා දෙකක් සපයයි, 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]] වේ.

සංයෝජන ලීට්කෝඩ් විසඳුම සඳහා ප්‍රවේශය

ගැටළුව සංයෝජන ලීට්කෝඩ් විසඳුම අපෙන් ඉල්ලා සිටියේ පළමු ස්වාභාවික සංඛ්‍යා වලින් 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 ට ඉහළින් සඳහන් කර ඇත්තේ ද්විමාන සංගුණකයයි.