Kombinasiya cəmi

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg eBay Facebook microsoft
Geyim Geri qayıtma RecursionBaxılıb 138

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.

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:
    1. Vursdakı bütün elementlərin cəmi verilmiş cəmdən az olana qədər arr [i] 'vec' vektoruna əlavə edin.
    2. Ə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.
    3. Vecdəki bütün elementlərin cəmi verilən cəmi aşarsa, nəticəyə heç bir şey əlavə etmirsiniz.
    4. 2 və 3-cü hadisələr baş verdikdə, son elementi vec-dən açın.
    5. i-ni növbəti sıra indeksinə keçir (yəni i ++).
    6. 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əmiPin

Kombinasiya cəmiPin

Kombinasiya cəmiPin

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

  1. Zamanın mürəkkəbliyi: T (n) = O (n * 2)n), n = massivin ölçüsü

References

Crack Sistemi Dizayn Müsahibələri
Translate »