संयोजन सम लेटेकोड समाधान


कठिनाई स्तर मध्यम
में अक्सर पूछा एडोब Airbnb वीरांगना सेब Atlassian ब्लूमबर्ग ByteDance ईबे Facebook गोल्डमैन सैक्स गूगल लिंक्डइन माइक्रोसॉफ्ट ओरेकल Snapchat चौकोर Uber VMware वॉलमार्ट लैब्स
ऐरे बैक ट्रैकिंग

समस्या संयोजन सम लेटेकोड सॉल्यूशन हमें प्रदान करता है सरणी या पूर्णांकों की सूची और एक लक्ष्य। हमें उन संयोजनों को खोजने के लिए कहा जाता है जो किसी भी समय दिए गए लक्ष्य को जोड़ने के लिए इन पूर्णांकों का उपयोग करके बनाया जा सकता है। इसलिए औपचारिक रूप से, हम दिए गए पूर्णांकों का उपयोग किसी भी संख्या में कर सकते हैं जैसे कि वे दिए गए लक्ष्य में जोड़ते हैं। आवश्यक आउटपुट संयोजन है जो दिए गए लक्ष्य के बराबर राशि है।

उदाहरणसंयोजन सम लेटेकोड समाधान

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 को दोहराया जाता है। हम यह सत्यापित कर सकते हैं कि दिए गए लक्ष्य तक सभी 3 आउटपुट योग हैं।

संयोजन सम लेटेकोड समाधान के लिए दृष्टिकोण

समस्या के लिए दृष्टिकोण सरल है। आमतौर पर, इस तरह की समस्याओं में, हमें बैकट्रैकिंग का उपयोग करना आवश्यक है। क्योंकि ऐसे सवालों में हमें पूरी खोज करने और उत्तर खोजने की आवश्यकता होती है। तो पहले, हम पूर्णांक की सूची को सॉर्ट करते हैं जो हमें दी गई है। बाद में, हम एक पुनरावर्ती कार्य बनाते हैं जो पूर्णांकों की वर्तमान अस्थायी सूची में पूर्णांक को जोड़ने और दिए गए लक्ष्य को जोड़ने के लिए आवश्यक शेष राशि का ट्रैक रखता है। तो पुनरावर्ती कार्य के अंदर, हम दो आधार मामलों को रखते हैं। पहला आधार मामला यह जांचना है कि क्या शेष राशि ऋणात्मक है या नहीं। उस स्थिति में, हम पुनरावर्ती फ़ंक्शन से वापस आ जाएंगे। शेष राशि शून्य के बराबर होने पर दूसरा आधार मामला हमारी आवश्यक स्थिति है। यदि शेष राशि शून्य है तो इसका मतलब है कि हम अपने आवश्यक लक्ष्य तक पहुँच चुके हैं। उस बिंदु पर, हम पूर्णांकों की वर्तमान अस्थायी सूची को सरणियों के आउटपुट सरणी में धकेलते हैं।

कोड

कॉम्बिनेशन सम लेटेकोड सॉल्यूशन के लिए C ++ कोड

#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

जटिलता विश्लेषण

समय जटिलता

O (N ^ (M / T + 1)) जहां N उम्मीदवारों की संख्या है, M सभी दिए गए पूर्णांकों में सबसे छोटा उम्मीदवार है, और T लक्ष्य मान है। इस प्रकार समय जटिलता घातीय है और यह अपेक्षित है क्योंकि एल्गोरिदम पुनरावर्ती है।

अंतरिक्ष जटिलता

O (T / M), जहां T लक्ष्य मान है और M अन्य सभी उम्मीदवारों के बीच न्यूनतम तत्व है।