संयोजन योग लेटकोड सोल्यूशन


अडचण पातळी मध्यम
वारंवार विचारले अडोब airbnb ऍमेझॉन सफरचंद Atlassian ब्लूमबर्ग बाइट डान्स हा कोड eBay फेसबुक गोल्डमन Sachs Google संलग्न मायक्रोसॉफ्ट ओरॅकल Snapchat स्क्वेअर उबेर व्हीएमवेअर वॉलमार्ट लॅब
अरे बॅकट्रॅकिंग

समस्‍याची जोड समेट लीटकोड सोल्यूशन आम्हाला एक प्रदान करते अॅरे किंवा पूर्णांकांची यादी आणि लक्ष्य. आम्हाला दिलेल्या लक्ष्यात भर घालण्यासाठी कितीही वेळा या पूर्णांकांचा वापर करून तयार करता येणारी संयोग शोधण्यासाठी सांगितले जाते. अधिक औपचारिकरित्या, आम्ही दिलेला पूर्णांक कितीही वेळा ते दिलेली लक्ष्यात वाढवू शकतो. आवश्यक आऊटपुट म्हणजे जोड्या ज्यात दिलेल्या लक्ष्याच्या बरोबरीची जोड असते.

उदाहरणसंयोजन योग लेटकोड सोल्यूशन

candidates = [2,3,6,7], target = 7
[[2,2,3],[7]]

स्पष्टीकरण: दिलेली आउटपुट दिलेल्या लक्ष्यापर्यंतची बेरीज करते. जरी आम्ही इतर कोणत्याही संयोजनासह येण्याचा प्रयत्न केला तरीही. आम्ही भिन्न क्रमांकावर समान पूर्णांकांची पूर्तता करू. परंतु ऑर्डरमध्ये केवळ जोड्या केल्याने फरक पडत नाही.

candidates = [2,3,5], target = 8
[[2,2,2,2],[2,3,3],[3,5]]

स्पष्टीकरणः आम्ही समान संख्या कितीही वेळा वापरु शकतो. आउटपुटमध्ये पहिल्या आउटपुटमध्ये आपण दोन वेळा वापरल्या आहेत. त्याचप्रमाणे दुसर्‍या आउटपुटमध्ये 2 ची पुनरावृत्ती होते. आम्ही दिलेल्या सत्यात सर्व 2 आउटपुटची बेरीज करू शकतो हे आम्ही सत्यापित करू शकतो.

कॉम्बीनेशन सम लेटकोड सोल्यूशनसाठी दृष्टिकोन

समस्येचा दृष्टीकोन शोधणे सोपे आहे. सामान्यत: यासारख्या समस्यांमध्ये आम्हाला बॅकट्रॅकिंग वापरण्याची आवश्यकता असते. कारण अशा प्रश्नांमध्ये आम्हाला संपूर्ण शोध घेणे आवश्यक आहे आणि उत्तर शोधणे आवश्यक आहे. प्रथम आपण दिलेली पूर्णांक यादी सॉर्ट करतो. त्यानंतर, आम्ही एक रिकर्सिव्ह फंक्शन तयार करतो जे सध्याच्या पूर्णांकांच्या तात्पुरत्या यादीमध्ये पूर्णांक जोडत राहते आणि दिलेल्या लक्ष्यात जोडण्यासाठी आवश्यक उर्वरित रकमेचा मागोवा ठेवत राहते. रिकर्सिव्ह फंक्शनमधे आम्ही दोन बेस केसेस ठेवतो. उर्वरित रकमेची रक्कम checkणात्मक झाली की नाही हे तपासणे हे पहिले बेस प्रकरण आहे. अशावेळी आम्ही रिकर्सिव्ह फंक्शनमधून परत येऊ. उर्वरित बेरीज शून्याइतकी असल्यास दुसरी बेस केस ही आपली आवश्यक अट आहे. जर उर्वरित रक्कम शून्य असेल तर याचा अर्थ असा आहे की आम्ही आमच्या आवश्यक उद्दिष्टावर पोहोचलो आहोत. त्या क्षणी आपण अ‍ॅरेच्या आऊटपुट अ‍ॅरे मध्ये पूर्णांकांची सद्य तात्पुरती यादी पुश करतो.

कोड

कॉम्बीनेशन सम लेटकोड सोल्यूशनसाठी सी ++ कोड

#include <bits/stdc++.h>
using namespace std;

void backtrack(vector<vector<int>> &output, vector<int> &current, vector<int> &candidates, int remain, int start){
    if(remain < 0)
        return;
    else if(remain == 0)output.push_back(current);
    else {
        for(int i=start;i<candidates.size();i++){
            current.push_back(candidates[i]);
            backtrack(output, current, candidates, remain - candidates[i], i);
            current.pop_back();
        }
    }
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> output;
    vector<int> current;
    sort(candidates.begin(), candidates.end());
    backtrack(output, current, candidates, target, 0);
    return output;
}

int main(){
  vector<int> cand = {2, 3, 6, 7};
  vector<vector<int>> output = combinationSum(cand, 7)	;
  for(auto x: output){
    for(auto y: x)
      cout<<y<<" ";
    cout<<endl;
  }
}
2 2 3 
7

कॉम्बिनेशन सम लेटकोड सोल्यूशनसाठी जावा कोड

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static List<List<Integer>> combinationSum(int[] nums, int target) {
      List<List<Integer>> list = new ArrayList<>();
      Arrays.sort(nums);
      backtrack(list, new ArrayList<>(), nums, target, 0);
      return list;
  }
  
  private static void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
      if(remain < 0) return;
      else if(remain == 0) list.add(new ArrayList<>(tempList));
      else{ 
          for(int i = start; i < nums.length; i++){
              tempList.add(nums[i]);
              backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
              tempList.remove(tempList.size() - 1);
          }
      }
  }

  public static void main (String[] args) throws java.lang.Exception
  {
    int[] nums = {2, 3, 6, 7};
    List<List<Integer>> output = combinationSum(nums, 7);
    for(List<Integer> x: output){
      for(Integer y: x)
        System.out.print(y+" ");
      System.out.println();
    }
  }
}
2 2 3
7

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन ^ (एम / टी + 1)) जिथे एन उमेदवारांची संख्या असते तिथे दिलेल्या सर्व पूर्णांकांमधील एम सर्वात लहान उमेदवार असतो आणि टी हे लक्ष्य मूल्य असते. अशा प्रकारे वेळची जटिलता घातीय असते आणि अशी अपेक्षा केली जाते कारण अल्गोरिदम रिकर्सिव बॅकट्रॅकिंग आहे.

स्पेस कॉम्प्लेक्सिटी

ओ (टी / एम), जिथे टी हे लक्ष्य मूल्य आहे आणि इतर सर्व उमेदवारांमध्ये एम हे किमान घटक आहेत.