සංයෝජන එකතුව ලීට්කෝඩ් විසඳුම


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇෙබෝ Airbnb ඇමේසන් Apple ජංගම දුරකථන ඇට්ලසියන් බ්ලූම්බර්ග් ByteDance ඊ බේ ෆේස්බුක් ගෝල්ඩ්මන් සැක්ස් ගූගල් LinkedIn මයික්රොසොෆ්ට් ඔරකල් 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 ලබා දී ඇති ඉලක්කයට සමාන බව අපට සත්‍යාපනය කළ හැකිය.

සංයෝජන එකතුව ලීට්කෝඩ් විසඳුම සඳහා ප්‍රවේශය

ගැටළුව සඳහා ප්රවේශය සොයා ගැනීම සරල ය. පොදුවේ ගත් කල, මෙවැනි ගැටළු වලදී, අප පසුබැසීම් භාවිතා කිරීම අවශ්‍ය වේ. මන්ද එවැනි ප්‍රශ්න වලදී අප විසින් සම්පූර්ණ සෙවීමක් කළ යුතු අතර පිළිතුර සොයාගත යුතුය. එබැවින් පළමුව, අපට ලබා දී ඇති පූර්ණ සංඛ්‍යා ලැයිස්තුව වර්ග කරමු. පසුව, අපි පුනරාවර්තන ශ්‍රිතයක් නිර්මාණය කරන අතර එය වර්තමාන තාවකාලික නිඛිල ලැයිස්තුවට පූර්ණ සංඛ්‍යාවක් එකතු කිරීම සහ ලබා දී ඇති ඉලක්කයට එකතු කිරීමට අවශ්‍ය ඉතිරි මුදල පිළිබඳව සොයා බැලීම දිගටම කරගෙන යයි. එබැවින් පුනරාවර්තන ශ්‍රිතය තුළ, අපි මූලික අවස්ථා දෙකක් තබා ගනිමු. පළමු මූලික නඩුව නම් අවශ්‍ය ඉතිරි මුදල .ණාත්මකද යන්න පරීක්ෂා කිරීමයි. එවැනි අවස්ථාවකදී, අපි පුනරාවර්තන ශ්‍රිතයෙන් නැවත පැමිණෙමු. දෙවන මුලික අවස්ථාව වන්නේ ඉතිරි මුදල ශුන්‍යයට සමාන නම් අපට අවශ්‍ය කොන්දේසියයි. ඉතිරි මුදල ශුන්‍ය නම් මෙයින් අදහස් කරන්නේ අප අපේ ඉලක්කයට ළඟා වී ඇති බවයි. එම අවස්ථාවෙහිදී, අපි වර්තමාන තාවකාලික නිඛිල ලැයිස්තුව අරා වල ප්‍රතිදාන පෙළට තල්ලු කරමු.

කේතය

සංයුක්ත එකතුව ලීට්කෝඩ් විසඳුම සඳහා සී ++ කේතය

#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 යනු ඉලක්කගත අගයයි. මේ අනුව කාල සංකීර්ණතාව on ාතීය වන අතර ඇල්ගොරිතම පුනරාවර්තන පසුගාමී වීම නිසා මෙය අපේක්ෂා කෙරේ.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (ටී / එම්), මෙහි T යනු ඉලක්කගත අගය වන අතර අනෙක් සියලුම අපේක්ෂකයින් අතර අවම මූලද්‍රව්‍යය M වේ.