കോമ്പിനേഷൻ തുക ലീറ്റ്കോഡ് പരിഹാരം


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു അഡോബി airbnb ആമസോൺ ആപ്പിൾ അത്ലഷിഅന് ബ്ലൂംബർഗ് ബൈറ്റ്ഡാൻസ് ബെ ഫേസ്ബുക്ക് ഗോൾഡ്മാൻ സാക്സ് ഗൂഗിൾ ലിങ്ക്ഡ് മൈക്രോസോഫ്റ്റ് ഒറാക്കിൾ Snapchat സമചതുരം യൂബർ വിഎംവെയർ വാൾമാർട്ട് ലാബുകൾ
അറേ ബാക്ക്ട്രാക്കിംഗ്

കോമ്പിനേഷൻ സം ലീറ്റ്കോഡ് പരിഹാരം ഞങ്ങൾക്ക് ഒരു പ്രശ്നം നൽകുന്നു ശ്രേണി അല്ലെങ്കിൽ പൂർണ്ണസംഖ്യകളുടെ പട്ടികയും ടാർഗെറ്റും. തന്നിരിക്കുന്ന ടാർഗെറ്റിലേക്ക് എത്ര തവണ വേണമെങ്കിലും ഈ സംഖ്യകൾ ഉപയോഗിച്ച് നിർമ്മിക്കാൻ കഴിയുന്ന കോമ്പിനേഷനുകൾ കണ്ടെത്താൻ ഞങ്ങളോട് പറയുന്നു. അതിനാൽ കൂടുതൽ ly പചാരികമായി, തന്നിരിക്കുന്ന സംഖ്യകൾ തന്നിരിക്കുന്ന ടാർഗെറ്റിലേക്ക് ചേർക്കുന്ന എത്ര തവണ വേണമെങ്കിലും ഉപയോഗിക്കാം. തന്നിരിക്കുന്ന ടാർഗറ്റിന് തുല്യമായ തുകയുള്ള കോമ്പിനേഷനുകളാണ് ആവശ്യമായ output ട്ട്‌പുട്ട്.

ഉദാഹരണംകോമ്പിനേഷൻ തുക ലീറ്റ്കോഡ് പരിഹാരം

candidates = [2,3,6,7], target = 7
[[2,2,3],[7]]

വിശദീകരണം: നൽകിയ output ട്ട്‌പുട്ട് തന്നിരിക്കുന്ന ടാർഗെറ്റിന് തുല്യമാണ്. മറ്റേതെങ്കിലും കോമ്പിനേഷനുമായി വരാൻ ഞങ്ങൾ ശ്രമിച്ചാലും. ഒരേ സംഖ്യകളെ മറ്റൊരു ക്രമത്തിൽ ക്രമീകരിക്കുന്നതിൽ ഞങ്ങൾ അവസാനിക്കും. എന്നാൽ കോമ്പിനേഷനുകൾ മാത്രം ചെയ്യുന്ന ക്രമം പ്രശ്നമല്ല.

candidates = [2,3,5], target = 8
[[2,2,2,2],[2,3,3],[3,5]]

വിശദീകരണം: നമുക്ക് ഒരേ സംഖ്യ എത്ര തവണ വേണമെങ്കിലും ഉപയോഗിക്കാം. Output ട്ട്‌പുട്ടിൽ, ആദ്യ .ട്ട്‌പുട്ടിൽ ഞങ്ങൾ 2 തവണ ഒന്നിലധികം തവണ ഉപയോഗിച്ചു. അതുപോലെ, രണ്ടാമത്തെ output ട്ട്‌പുട്ടിൽ 2 ആവർത്തിക്കുന്നു. എല്ലാ 3 p ട്ട്‌പുട്ടുകളും തന്നിരിക്കുന്ന ടാർഗെറ്റിന് തുല്യമാണെന്ന് ഞങ്ങൾക്ക് സ്ഥിരീകരിക്കാൻ കഴിയും.

കോമ്പിനേഷൻ സം ലീറ്റ്കോഡ് പരിഹാരത്തിനുള്ള സമീപനം

പ്രശ്നത്തിനുള്ള സമീപനം കണ്ടെത്താൻ ലളിതമാണ്. സാധാരണയായി, ഇതുപോലുള്ള പ്രശ്നങ്ങളിൽ, ഞങ്ങൾ ബാക്ക്ട്രാക്കിംഗ് ഉപയോഗിക്കേണ്ടതുണ്ട്. കാരണം അത്തരം ചോദ്യങ്ങളിൽ‌ ഞങ്ങൾ‌ ഒരു സമ്പൂർ‌ണ്ണ തിരയൽ‌ നടത്തി ഉത്തരം കണ്ടെത്തേണ്ടതുണ്ട്. അതിനാൽ ആദ്യം, ഞങ്ങൾക്ക് നൽകിയിരിക്കുന്ന പൂർണ്ണസംഖ്യകളുടെ പട്ടിക ഞങ്ങൾ അടുക്കുന്നു. അതിനുശേഷം, ഞങ്ങൾ‌ ഒരു ആവർത്തന പ്രവർ‌ത്തനം സൃഷ്‌ടിക്കുന്നു, അത് നിലവിലുള്ള താൽ‌ക്കാലിക സംഖ്യകളുടെ പട്ടികയിലേക്ക് ഒരു സംഖ്യ ചേർ‌ക്കുകയും തന്നിരിക്കുന്ന ടാർ‌ഗെറ്റ് വരെ ചേർ‌ക്കുന്നതിന് ആവശ്യമായ ബാക്കി തുകയുടെ ട്രാക്ക് സൂക്ഷിക്കുകയും ചെയ്യുന്നു. അതിനാൽ ആവർത്തന ഫംഗ്ഷനുള്ളിൽ, ഞങ്ങൾ രണ്ട് അടിസ്ഥാന കേസുകൾ സൂക്ഷിക്കുന്നു. ആവശ്യമായ ബാക്കി തുക നെഗറ്റീവ് ആണോ എന്ന് പരിശോധിക്കുക എന്നതാണ് ആദ്യത്തെ അടിസ്ഥാന കേസ്. അത്തരം സന്ദർഭങ്ങളിൽ, ഞങ്ങൾ ആവർത്തന പ്രവർത്തനത്തിൽ നിന്ന് മടങ്ങും. ശേഷിക്കുന്ന തുക പൂജ്യത്തിന് തുല്യമാണെങ്കിൽ രണ്ടാമത്തെ അടിസ്ഥാന കേസ് ഞങ്ങൾക്ക് ആവശ്യമായ അവസ്ഥയാണ്. ശേഷിക്കുന്ന തുക പൂജ്യമാണെങ്കിൽ ഇതിനർത്ഥം ഞങ്ങൾ ആവശ്യമായ ലക്ഷ്യത്തിലെത്തിയെന്നാണ്. ആ സമയത്ത്, ഞങ്ങൾ സംഖ്യകളുടെ നിലവിലെ താൽക്കാലിക പട്ടിക അറേകളുടെ output ട്ട്‌പുട്ട് അറേയിലേക്ക് തള്ളുന്നു.

കോഡ്

കോമ്പിനേഷൻ സം ലീറ്റ്കോഡ് പരിഹാരത്തിനായുള്ള സി ++ കോഡ്

#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), ഇവിടെ ടി എന്നത് ടാർഗെറ്റ് മൂല്യവും മറ്റെല്ലാ കാൻഡിഡേറ്റുകളിലും ഏറ്റവും കുറഞ്ഞ ഘടകമാണ് എം.