Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.
Birləşmə cəmi problemində bir array müsbət tam ədədi arr [] və cəmi s, arr [] da bu elementlərin cəminin bərabər olduğu bütün unikal birləşmələrini tapın s. Eyni təkrarlanan sayı arr [] -dən sınırsız dəfə seçilə bilər. Hər bir birləşmənin elementləri irəliləməyən qaydada çap olunmalıdır.
Kombinasiyaların özü artan qaydada sıralanmalıdır, yəni ilk kiçik elementlə birləşmə əvvəlcə çap olunmalıdır. Mümkün birləşmə yoxdursa, “Belə birləşmə tapılmadı” yazdırın.
Mündəricat
Nümunələr
Input: arr[] = [2,3,5,8], sum = 8
Output: [2, 2, 2, 2]
[2, 3, 3]
[3, 5]
[8]
Input: arr[] = [2,4,6,8], sum = 11
Output: No such combination found
Input: arr[] = [3,5,6,11], sum = 19
Output: [3, 3, 3, 5, 5]
[3, 5, 5, 6]
[3, 5, 11]
Kombinasiya cəmi üçün alqoritm
- Dizini artan qaydada çeşidləyin.
- Bütün cüt elementləri massivdən silin.
- Geri qayıtma və rekursiyadan aşağıdakı şəkildə istifadə edin:
- Vursdakı bütün elementlərin cəmi verilmiş cəmdən az olana qədər arr [i] 'vec' vektoruna əlavə edin.
- Əgər vecdəki bütün elementlərin cəmi verilmiş cəmə bərabər olarsa, 'nəticə' yə (vektorların vektoru) vec əlavə edin.
- Vecdəki bütün elementlərin cəmi verilən cəmi aşarsa, nəticəyə heç bir şey əlavə etmirsiniz.
- 2 və 3-cü hadisələr baş verdikdə, son elementi vec-dən açın.
- i-ni növbəti sıra indeksinə keçir (yəni i ++).
- müəyyən bir cəmi olan bütün kombinasiyalar nəticəyə əlavə olunana qədər 1-4 addımlarını təkrarlayın.
Kombinasiya cəmi üçün tətbiqetmə
C ++ Proqramı
#include <bits/stdc++.h>
using namespace std;
// function to find all combinations of
// elements of an array that add upto a given sum
void findCombination(vector<int> &arr, int sum,
vector<vector<int>> &result,
vector<int> &vec, int i)
{
// sum of elements in vec becomes greater than original sum
if (sum < 0)
return;
// sum of elements in vec is exactly equal to original sum
if (sum == 0)
{
// add that particular combination to result
result.push_back(vec);
return;
}
// recur for all remaining elements that
// have value smaller than original sum.
while (i < arr.size() && sum-arr[i] >= 0)
{
// add every element of the array to the vec starting from i
// that adds/contributes to 'sum'
vec.push_back(arr[i]);
// recur to adding arr[i] to vec
// if it contributes to 'sum'
findCombination(arr, sum - arr[i], result, vec, i);
// move to next element in case
// sum of elements becomes greater than
// or equal to the required sum
i++;
// remove the last number from the combination list
// to add next element (basically backtracking)
vec.pop_back();
}
}
// Returns all combinations of arr[] that have given sum.
vector<vector<int> > combinationSum(vector<int>& arr, int sum)
{
// sort input array
sort(arr.begin(), arr.end());
// remove duplicates
// create an array to add all the unique elements to it
vector <int> uniq;
// create a set to check whether an element
// has been added to unique array or not
unordered_set <int> us;
for(auto i : arr)
{
if(us.find(i) == us.end())
{
us.insert(i);
uniq.push_back(i);
}
}
// copy the unique array back to original array
arr = uniq;
// to store a unique combination
vector<int> vec;
// stores all the unique combinations
vector<vector<int>> result;
findCombination(arr, sum, result, vec, 0);
return result;
}
// implementing above functions
int main()
{
vector<int> arr = {2,3,5,8};
int n = arr.size();
int sum = 8;
vector<vector<int>> result = combinationSum(arr, sum);
// If result vector is empty
// no combinations of array elements with given sum exist
if (result.empty())
{
cout << "No such combination found";
return 0;
}
// Print all combinations stored in result.
for (int i = 0; i < result.size(); i++)
{
if (!result[i].empty())
{
cout << "[ ";
for (int j = 0; j < result[i].size(); j++)
cout << result[i][j] << " ";
cout << "]";
}
cout<<endl;
}
return 0;
}
[ 2 2 2 2 ] [ 2 3 3 ] [ 3 5 ] [ 8 ]
Java Proqramı
import java.util.*;
import java.io.*;
class tutorialcup
{
// function to find all combinations of
// elements of an array that add upto a given sum
static void findCombination(ArrayList<Integer> arr, int sum,
ArrayList<ArrayList<Integer>> result,
ArrayList<Integer> vec, int i)
{
// sum of elements in vec becomes greater than original sum
if (sum < 0)
return;
// sum of elements in vec is exactly equal to original sum
if (sum == 0)
{
// add that particular combination to result
result.add(new ArrayList<Integer>(vec));
return;
}
// recur for all remaining elements that
// have value smaller than original sum.
while (i < arr.size() && sum-arr.get(i) >= 0)
{
// add every element of the array to the vec starting from i
// that adds/contributes to 'sum'
vec.add(arr.get(i));
// recur to adding arr[i] to vec
// if it contributes to 'sum'
findCombination(arr, sum - arr.get(i), result, vec, i);
// move to next element in case
// sum of elements becomes greater than
// or equal to the required sum
i++;
// remove the last number from the combination list
// to add next element(basically backtracking)
vec.remove(vec.size()-1);
}
}
// Returns all combinations of arr[] that have given sum.
static ArrayList<ArrayList<Integer>> combinationSum(ArrayList<Integer> arr, int sum)
{
// sort input array
Collections.sort(arr);
// remove duplicates
// create an array to add all the unique elements to it
ArrayList <Integer> uniq = new ArrayList<Integer>();
// create a set to check whether an element
// has been added to unique array or not
HashSet <Integer> hs = new HashSet <Integer>();
for(int i=0;i<arr.size();i++)
{
if(hs.contains(arr.get(i)) == false)
{
hs.add(arr.get(i));
uniq.add(arr.get(i));
}
}
// copy the unique array back to original array
arr = uniq;
// to store a unique combination
ArrayList <Integer> vec = new ArrayList <Integer>();
// stores all the unique combinations
ArrayList <ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
findCombination(arr, sum, result, vec, 0);
return result;
}
// implementing above function
public static void main(String args[])
{
ArrayList <Integer> arr = new ArrayList <Integer> (Arrays.asList(2,3,5,8));
int n = arr.size();
int sum = 8;
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
result = combinationSum(arr, sum);
// If result vector is empty
// no combinations of array elements with given sum exist
if (result.isEmpty())
{
System.out.println("No such combination found");
return;
}
for(int i=0;i<result.size();i++)
System.out.println(result.get(i));
}
}
[2, 2, 2, 2] [2, 3, 3] [3, 5] [8]
Kombinasiya Cəmi üçün Mürəkkəblik Analizi
- Zamanın mürəkkəbliyi: T (n) = O (n * 2)n), n = massivin ölçüsü
