கூட்டுத் தொகை லீட்கோட் தீர்வு


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அடோப் airbnb அமேசான் ஆப்பிள் அட்லாசியன் ப்ளூம்பெர்க் ByteDance ஈபே பேஸ்புக் கோல்ட்மேன் சாக்ஸ் கூகிள் லின்க்டு இன் மைக்ரோசாப்ட் ஆரக்கிள் SnapChat சதுக்கத்தில் கிழித்து , 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 வெளியீடுகளும் கொடுக்கப்பட்ட இலக்குக்கு சமம் என்பதை நாங்கள் சரிபார்க்க முடியும்.

கூட்டுத் தொகை லீட்கோட் தீர்வுக்கான அணுகுமுறை

சிக்கலுக்கான அணுகுமுறை கண்டுபிடிக்க எளிதானது. பொதுவாக, இது போன்ற சிக்கல்களில், நாங்கள் பின்வாங்கலைப் பயன்படுத்த வேண்டும். ஏனெனில் இதுபோன்ற கேள்விகளில் நாம் ஒரு முழுமையான தேடலை மேற்கொண்டு பதிலைக் கண்டுபிடிக்க வேண்டும். எனவே முதலில், எங்களுக்கு வழங்கப்பட்ட முழு எண்களின் பட்டியலை வரிசைப்படுத்துகிறோம். பின்னர், நாங்கள் ஒரு சுழல்நிலை செயல்பாட்டை உருவாக்குகிறோம், இது தற்போதைய தற்காலிக முழு எண்களின் பட்டியலில் ஒரு முழு எண்ணைச் சேர்ப்பதையும், கொடுக்கப்பட்ட இலக்கைச் சேர்க்கத் தேவையான மீதமுள்ள தொகையைக் கண்காணிப்பதையும் தொடர்கிறது. எனவே சுழல்நிலை செயல்பாட்டின் உள்ளே, நாங்கள் இரண்டு அடிப்படை நிகழ்வுகளை வைத்திருக்கிறோம். மீதமுள்ள அடிப்படை தொகை எதிர்மறையாக இருக்கிறதா என்று சோதிப்பது முதல் அடிப்படை வழக்கு. அவ்வாறான நிலையில், சுழல்நிலை செயல்பாட்டிலிருந்து திரும்புவோம். மீதமுள்ள தொகை பூஜ்ஜியத்திற்கு சமமாக இருந்தால் இரண்டாவது அடிப்படை வழக்கு நமக்கு தேவையான நிபந்தனையாகும். மீதமுள்ள தொகை பூஜ்ஜியமாக இருந்தால், இதன் பொருள் நாம் தேவையான இலக்கை அடைந்துவிட்டோம். அந்த நேரத்தில், எண்களின் தற்போதைய தற்காலிக பட்டியலை வரிசைகளின் வெளியீட்டு வரிசையில் தள்ளுகிறோம்.

குறியீடு

கூட்டுத் தொகை லீட்கோட் தீர்வுக்கான சி ++ குறியீடு

#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 என்பது இலக்கு மதிப்பு. இதனால் நேர சிக்கலானது அதிவேகமானது மற்றும் இது எதிர்பார்க்கப்படுகிறது, ஏனெனில் வழிமுறை மறுநிகழ்வு பின்னடைவு ஆகும்.

விண்வெளி சிக்கலானது

ஓ (டி / எம்), T என்பது இலக்கு மதிப்பு மற்றும் மற்ற அனைத்து வேட்பாளர்களிடையே M என்பது குறைந்தபட்ச உறுப்பு ஆகும்.