ጥምረት ድምር Leetcode መፍትሔ  


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ የ Adobe Airbnb አማዞን ፓም Atlassian ብሉምበርግ ByteDance eBay ፌስቡክ ጎልድማን ሳክስ google LinkedIn የ Microsoft በ Oracle Snapchat አራት ማዕዘን በ Uber VMware የዎልማርት ላብራቶሪዎች
ስልተ ሰልፍ ወደ ኋላ መመለስ ምስጠራ ቃለ መጠይቅ interviewprep ሊት ኮድ LeetCodeSolutions

ችግሩ የውህደት ድምር Leetcode መፍትሔ ለእኛ ይሰጠናል ደርድር ወይም የቁጥር እና ዒላማ ዝርዝር። የተሰጠውን ዒላማ በሚጨምሩበት በማንኛውም ጊዜ እነዚህን ኢንቲጀሮች በመጠቀም ሊሠሩ የሚችሉትን ውህዶች እንዲያገኙ ተነግሮናል ፡፡ ስለዚህ በመደበኛነት የተሰጡትን ቁጥሮች በተጠቀሰው ዒላማ ላይ እንደሚጨምሩ በማንኛውም ቁጥር ልንጠቀምባቸው እንችላለን ፡፡ የሚፈለገው ውጤት ከተጠቀሰው ዒላማ ጋር እኩል የሆነ ድምር ያላቸው ውህዶች ናቸው ፡፡

ለምሳሌጥምረት ድምር 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]]

ማብራሪያ-ተመሳሳይ ቁጥር (ኢንቲጀር) በማንኛውም ጊዜ ልንጠቀምበት ስለምንችል ፡፡ በውጤቱ ውስጥ በመጀመሪያው ውፅዓት ውስጥ 2 ብዙ ጊዜዎችን ተጠቅመናል ፡፡ በተመሳሳይ ፣ በሁለተኛው ውጤት 2 ተደግሟል ፡፡ ሁሉም 3 ውፅአቶች ለተሰጠው ዒላማ መጠቀማቸውን ማረጋገጥ እንችላለን ፡፡

የውህደት ድምር Leetcode መፍትሄ አቀራረብ  

ለችግሩ አቀራረብ ቀላል ነው ፡፡ በአጠቃላይ ፣ እንደዚህ ባሉ ችግሮች ውስጥ ፣ የኋላ መመለሻን እንድንጠቀም ይጠበቅብናል ፡፡ ምክንያቱም በእንደዚህ ዓይነት ጥያቄዎች ውስጥ የተሟላ ፍለጋ ማድረግ እና መልሱን መፈለግ ይጠበቅብናል ፡፡ ስለዚህ በመጀመሪያ እኛ የተሰጠንን የቁጥር ቁጥሮች ዝርዝር እናደርጋለን ፡፡ ከዚያ በኋላ አሁን ባለው ጊዜያዊ የቁጥር ዝርዝር ውስጥ ኢንቲጀር መጨመር እና የተሰጠውን ዒላማ ለመደመር የሚያስፈልገውን ቀሪ ገንዘብ መከታተልን የሚቀጥል ተደጋጋሚ ተግባር እንፈጥራለን ፡፡ ስለዚህ በእንደገና ተግባር ውስጥ ሁለት መሰረታዊ ጉዳዮችን እንጠብቃለን ፡፡ የመጀመሪያው የመሠረት ጉዳይ የሚፈለገው ቀሪው ድምር አሉታዊ ከሆነ ማረጋገጥ ነው ፡፡ ያ ከሆነ እኛ እንደገና ከተሰራው ተግባር እንመለሳለን ፡፡ ቀሪው ድምር ከዜሮ ጋር እኩል ከሆነ ሁለተኛው መሰረታዊ ጉዳይ የእኛ አስፈላጊ ሁኔታ ነው ፡፡ ቀሪው ድምር ዜሮ ከሆነ ይህ ማለት የምንፈልገውን ግብ ላይ ደርሰናል ማለት ነው ፡፡ በዚያን ጊዜ የአሁኑን ጊዜያዊ የቁጥር ዝርዝር ወደ ውፅዓት ድርድር እንገፋፋለን ፡፡

ተመልከት
የሳንቲም ለውጥ ችግር

ኮድ  

የ C ++ ኮድ ለ ‹ጥምረት› ድምር Leetcode Solution

#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

የጃቫ ኮድ ለምርምር ድምር 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

ውስብስብነት ትንተና  

የጊዜ ውስብስብነት

ኦ (N ^ (M / T + 1)) N የእጩዎች ቁጥር ባለበት ፣ M ከተሰጡት ቁጥሮች ሁሉ ውስጥ ትንሹ እጩ ሲሆን ቲ ደግሞ የታለመው እሴት ነው። ስለሆነም የጊዜ ውስብስብነቱ እጅግ ሰፊ ነው እናም ይህ የሚጠበቅ ነው ምክንያቱም ስልተ ቀመሙ እንደገና መመለሻ ነው።

የቦታ ውስብስብነት

ኦ (ቲ / ኤም) ፣ የትኛውም ኢላማው እሴቱ ሲሆን M በሁሉም ሌሎች እጩዎች መካከል አነስተኛ ንጥረ ነገር ነው ፡፡

1