ترکیبات راه حل کد


سطح دشواری متوسط
اغلب در خشت آمازون سیب فیس بوک گوگل مایکروسافت یاهو
عقب نشینی

مسئله Combinations Leetcode Solution دو عدد صحیح n و k برای ما فراهم می کند. به ما گفته می شود که تمام توالی هایی را که k عناصر از n عنصر از 1 تا n انتخاب کرده اند ، تولید کنید. ما این توالی ها را به صورت صف. اجازه دهید چند مثال را مرور کنیم تا درک بهتری از مشکل داشته باشیم.

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

توضیحات: خروجی همه روشهای انتخاب عناصر k از اولین n عدد طبیعی را نشان می دهد. در اینجا ، ترتیب اعداد مهم نیست. فقط مجموعه اعداد مهم است.

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

توضیح: در اینجا ، از آنجا که ما یک عنصر واحد داریم. همچنین به ما گفته می شود که یک عنصر را انتخاب کنید. بنابراین خروجی [[1]] است.

رویکرد برای راه حل کد ترکیبی

مسئله Combations Leetcode Solution به سادگی از ما خواسته است که تمام توالی های انتخاب عناصر k را از اولین n عدد طبیعی تولید کنیم. بنابراین ، این به سادگی تولید همه ترکیبات nCk موجود برای انتخاب عناصر k است. به طور کلی ، وظایف مربوط به تولید توالی با استفاده از بازگشت حل می شود. بنابراین ، ما یک رویکرد بازگشتی به مسئله را امتحان می کنیم. و برداری را با هدف ذخیره چنین ترکیباتی دنبال کنید.

بنابراین ، ما با یک بردار خالی شروع می کنیم. ما یک عنصر را به درون آن فشار می دهیم. سپس یک حل مسئله از انتخاب عناصر k-1 از عناصر باقی مانده n-1 را به صورت بازگشتی حل کنید. به این ترتیب ما همچنان مشکل را کاهش می دهیم تا زمانی که به مشکل انتخاب 0 عنصر برسیم. وقتی این اتفاق می افتد ، ما این بردار موقتی را به جواب خود می رسانیم. در پایان ، این پاسخ تمام توالی های انتخاب k عناصر از n عنصر را ذخیره می کند.

ترکیبات راه حل کد

کد برای ترکیبات راه حل کد

کد ++ C

#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 به معنی ضریب دوجمله ای انتخاب k عناصر از n عنصر است.

پیچیدگی فضا

O (nCk) ، همانطور که در بالا nCk بیان شد در اینجا به ضریب دو جمله ای اشاره دارد.