संयोजन Sum Leetcode समाधान


कठिनाई तह मध्यम
बारम्बार सोधिन्छ एडोब airbnb अमेजन एप्पल Atlassian ब्लूमबर्ग बाइटडेन्स eBay फेसबुक Goldman सैक्स गुगल LinkedIn माइक्रोसफ्ट बजेट Snapchat स्क्वायर Uber VMware वालमार्ट ल्याबहरू
एरे ब्याकट्र्याकिंग

समस्या संयोजन Sum Leetcode समाधान हामीलाई प्रदान गर्दछ array वा पूर्णांकको सूची र लक्ष्य। हामीलाई संयोजनहरू पत्ता लगाउन भनिएको छ जुन ईन्टेजरहरू प्रयोग गर्न सकिन्छ कुनै पनि समय प्रदान गरिएको लक्ष्यमा थपिन्छ। अधिक औपचारिक रूपमा, हामी दिइएको पूर्णाgers्क कुनै धेरै पटक प्रयोग गर्न सक्दछौं जुन उनीहरूले दिइएको लक्षितमा थप्दछन्। आवश्यक आउटपुट संयोजन हो जुन दिइएको लक्षितको बराबर योग हुन्छ।

उदाहरणकासंयोजन Sum Leetcode समाधान

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

स्पष्टीकरण: किनकि हामी समान इन्टिजर कुनै पनि संख्याको प्रयोग गर्न सक्दछौं। आउटपुटमा, हामीले पहिलो आउटपुटमा २ बहु पटक प्रयोग गरेका छौं। त्यस्तै, दोस्रो आउटपुटमा २ दोहोरिन्छ। हामी प्रमाणित गर्न सक्दछौं कि दिइएको लक्ष्यमा सबै target आउटपुटहरूको जोड।

संयोजन Sum Leetcode समाधानको लागि दृष्टिकोण

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

कोड

C ++ कोड संयोजन Sum Leetcode समाधानको लागि

#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

संयोजन Sum Leetcode समाधानको लागि जाभा कोड

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 + १)) जहाँ एन उम्मेदवारहरूको संख्या हो, M सबै दिशानिर्देशहरू मध्ये सब भन्दा सानो उम्मेद्वार हो, र T लक्षित मान हो। यसैले समय जटिलता घातीय हुन्छ र यो आशा गरिन्छ किनकि एल्गोरिथ्म रिकर्सिव ब्याकट्र्याकिंग हो।

ठाउँ जटिलता

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