ಸಂಯೋಜನೆಗಳು ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಡೋಬ್ ಅಮೆಜಾನ್ ಆಪಲ್ ಫೇಸ್ಬುಕ್ ಗೂಗಲ್ ಮೈಕ್ರೋಸಾಫ್ಟ್ ಯಾಹೂ
ಬ್ಯಾಕ್‌ಟ್ರಾಕಿಂಗ್

ಕಾಂಬಿನೇಶನ್ಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವು ನಮಗೆ ಎರಡು ಮತ್ತು ಪೂರ್ಣಾಂಕಗಳಾದ ಪೂರ್ಣಾಂಕಗಳನ್ನು ಒದಗಿಸುತ್ತದೆ. 1 ರಿಂದ n ಗೆ n ಅಂಶಗಳಿಂದ ಕೆ ಅಂಶಗಳನ್ನು ಹೊಂದಿರುವ ಎಲ್ಲಾ ಅನುಕ್ರಮಗಳನ್ನು ಉತ್ಪಾದಿಸಲು ನಮಗೆ ತಿಳಿಸಲಾಗಿದೆ. ನಾವು ಈ ಅನುಕ್ರಮಗಳನ್ನು ಒಂದು ಎಂದು ಹಿಂದಿರುಗಿಸುತ್ತೇವೆ ಸರಣಿ. ಸಮಸ್ಯೆಯ ಬಗ್ಗೆ ಉತ್ತಮ ತಿಳುವಳಿಕೆಯನ್ನು ಪಡೆಯಲು ನಾವು ಕೆಲವು ಉದಾಹರಣೆಗಳ ಮೂಲಕ ಹೋಗೋಣ.

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

ವಿವರಣೆ: n ಟ್ಪುಟ್ ಮೊದಲ n ನೈಸರ್ಗಿಕ ಸಂಖ್ಯೆಗಳಿಂದ ಕೆ ಅಂಶಗಳನ್ನು ಆರಿಸುವ ಎಲ್ಲಾ ವಿಧಾನಗಳನ್ನು ತೋರಿಸುತ್ತದೆ. ಇಲ್ಲಿ, ಸಂಖ್ಯೆಗಳ ಆದೇಶವು ಅಪ್ರಸ್ತುತವಾಗುತ್ತದೆ. ಸಂಖ್ಯೆಗಳ ಸಂಗ್ರಹ ಮಾತ್ರ ಮುಖ್ಯವಾಗಿದೆ.

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

ವಿವರಣೆ: ಇಲ್ಲಿ, ನಮ್ಮಲ್ಲಿ ಒಂದೇ ಅಂಶ ಇರುವುದರಿಂದ. ಒಂದೇ ಅಂಶವನ್ನು ಆರಿಸಲು ಸಹ ನಮಗೆ ತಿಳಿಸಲಾಗಿದೆ. ಹೀಗಾಗಿ output ಟ್‌ಪುಟ್ [[1]] ಆಗಿದೆ.

ಸಂಯೋಜನೆಗಳ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಾಗಿ ಅನುಸಂಧಾನ

ಸಮಸ್ಯೆ ಕಾಂಬಿನೇಶನ್ಸ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವು ಮೊದಲ n ನೈಸರ್ಗಿಕ ಸಂಖ್ಯೆಗಳಿಂದ ಕೆ ಅಂಶಗಳನ್ನು ಆರಿಸುವ ಎಲ್ಲಾ ಅನುಕ್ರಮಗಳನ್ನು ರಚಿಸಲು ಕೇಳಿದೆ. ಆದ್ದರಿಂದ, ಇದು ಕೆ ಅಂಶಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳಲು ಲಭ್ಯವಿರುವ ಎಲ್ಲಾ ಎನ್‌ಸಿಕೆ ಸಂಯೋಜನೆಗಳನ್ನು ಸರಳವಾಗಿ ಉತ್ಪಾದಿಸುತ್ತಿದೆ. ಸಾಮಾನ್ಯವಾಗಿ, ಅನುಕ್ರಮಗಳ ಪೀಳಿಗೆಯನ್ನು ಒಳಗೊಂಡ ಕಾರ್ಯಗಳನ್ನು ಪುನರಾವರ್ತನೆಯನ್ನು ಬಳಸಿಕೊಂಡು ಪರಿಹರಿಸಲಾಗುತ್ತದೆ. ಆದ್ದರಿಂದ, ನಾವು ಸಮಸ್ಯೆಗೆ ಪುನರಾವರ್ತಿತ ವಿಧಾನವನ್ನು ಪ್ರಯತ್ನಿಸುತ್ತೇವೆ. ಮತ್ತು ಅಂತಹ ಸಂಯೋಜನೆಗಳನ್ನು ಸಂಗ್ರಹಿಸುವ ಗುರಿಯನ್ನು ಹೊಂದಿರುವ ವೆಕ್ಟರ್ ಅನ್ನು ಟ್ರ್ಯಾಕ್ ಮಾಡಿ.

ಆದ್ದರಿಂದ, ನಾವು ಖಾಲಿ ವೆಕ್ಟರ್ನೊಂದಿಗೆ ಪ್ರಾರಂಭಿಸುತ್ತೇವೆ. ನಾವು ಅದರಲ್ಲಿ ಒಂದು ಅಂಶವನ್ನು ತಳ್ಳುತ್ತೇವೆ. ನಂತರ ಉಳಿದ 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 ಅಂಶಗಳನ್ನು ಆರಿಸುವ ದ್ವಿಪದ ಗುಣಾಂಕ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್‌ಸಿಕೆ), ಇಲ್ಲಿ nCk ಮೇಲೆ ಹೇಳಿದಂತೆ ದ್ವಿಪದ ಗುಣಾಂಕವನ್ನು ಸೂಚಿಸುತ್ತದೆ.