Комбинација Леетцоде решење


Ниво тешкоће Средњи
Често питани у адобе амазонка јабука фацебоок гоогле мицрософт иахоо
Бацктрацкинг

Проблем Комбинације Леетцоде Солутион пружа нам две целобројне вредности, н и к. Речено нам је да генеришемо све секвенце које имају к елемената одабраних од н елемената од 1 до н. Те секвенце враћамо као поредак. Прођимо кроз неколико примера да бисмо боље разумели проблем.

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

Објашњење: Излаз приказује све начине бирања к елемената из првих н природних бројева. Овде редослед бројева није битан. Важна је само колекција бројева.

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

Објашњење: Ево, пошто имамо један елемент. Такође нам је речено да одаберемо један елемент. Тако је излаз [[1]].

Приступ за комбинацију Леетцоде решења

Проблем Комбинације Леетцоде Солутион тражили су од нас да једноставно генеришемо све секвенце бирања к елемената из првих н природних бројева. Дакле, ово једноставно генерише све комбинације нЦк доступне за одабир к елемената. Генерално се задаци који укључују генерисање секвенци решавају помоћу рекурзије. Дакле, покушавамо рекурзивни приступ проблему. И водите евиденцију вектора чији је циљ да ускладишти такве комбинације.

Дакле, почињемо са празним вектором. У њега угурамо елемент. Затим рекурзивно решите потпроблем одабира к-1 елемената од преосталих н-1 елемената. на тај начин настављамо да смањујемо проблем све док не дођемо до проблема одабира 0 елемената. Када се то догоди, потиснемо овај привремени вектор на наш одговор. На крају, овај одговор чува све секвенце бирања к елемената из н елемената.

Комбинација Леетцоде решење

Шифра за комбинацију Леетцоде решење

Ц ++ код

#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]]

Анализа сложености

Сложеност времена

О (к * нЦк), овде нЦк означава биномни коефицијент одабира к елемената из н елемената.

Сложеност простора

О (нЦк), као што је горе наведено, нЦк се овде односи на биномни коефицијент.