조합 합계

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 이베이 Facebook Microsoft
배열 역 추적 재귀조회수 139

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

조합 합계 문제에서 우리는 정렬 양의 정수 arr [] 그리고 합계 s, arr []에서 요소의 합이 다음과 같은 모든 고유 한 요소 조합을 찾습니다. s. arr []에서 동일한 반복 수를 무제한으로 선택할 수 있습니다. 각 조합의 요소는 내림차순이 아닌 순서로 인쇄되어야합니다.
조합 자체는 오름차순으로 정렬되어야합니다. 즉, 가장 작은 첫 번째 요소가있는 조합이 먼저 인쇄되어야합니다. 가능한 조합이 없으면 "No such combination found"를 인쇄합니다.

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]

조합 합계 알고리즘

  • 오름차순으로 배열을 정렬합니다.
  • 배열에서 모든 중복 요소를 제거하십시오.
  • 다음과 같은 방법으로 역 추적 및 재귀를 사용합니다.
    1. vec의 모든 요소의 합이 주어진 합보다 작을 때까지 arr [i]를 벡터 'vec'에 재귀 적으로 추가합니다.
    2. vec의 모든 요소의 합이 주어진 합과 같으면 vec를 'result'(벡터의 벡터)에 추가합니다.
    3. vec의 모든 요소의 합계가 주어진 합계를 초과하면 결과에 아무것도 추가하지 않습니다.
    4. 케이스 2와 3이 발생하면 vec에서 마지막 요소를 팝합니다.
    5. i를 다음 배열 인덱스 (예 : i ++)로 이동합니다.
    6. 주어진 합계를 가진 모든 조합이 결과에 추가 될 때까지 1-4 단계를 반복합니다.

조합 합계

조합 합계

조합 합계

조합 합계 구현

C ++ 프로그램

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

자바 프로그램

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]

조합 합계에 대한 복잡성 분석

  1. 시간 복잡도 : T (n) = O (n * 2n), n = 배열 ​​크기

참조

균열 시스템 설계 인터뷰
Translate »