સંયોજનનો સરવાળો લીટકોડ સોલ્યુશન


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એડોબ Airbnb એમેઝોન સફરજન Atlassian બ્લૂમબર્ગ ByteDance ઇબે ફેસબુક ગોલ્ડમૅન સૅશ Google LinkedIn માઈક્રોસોફ્ટ ઓરેકલ Snapchat સ્ક્વેર ઉબેર વીએમવેર વોલમાર્ટ લેબ્સ
અરે બેકટ્રેકીંગ

સમસ્યા કોમ્બીનેશન સમ લીટકોડ સોલ્યુશન અમને પ્રદાન કરે છે એરે અથવા પૂર્ણાંકોની સૂચિ અને લક્ષ્ય. અમને તે સંયોજનો શોધવા માટે કહેવામાં આવે છે જે આપેલ લક્ષ્યમાં ઉમેરો તે સંખ્યાને આ પૂર્ણાંકોની મદદથી કરી શકાય છે. તેથી વધુ formalપચારિક રીતે, આપણે આપેલ પૂર્ણાંકોનો ઉપયોગ ગમે તેટલા વખત કરીશું જે તેઓ આપેલ લક્ષ્યમાં ઉમેરે છે. આવશ્યક આઉટપુટ એ સંયોજનો છે જે આપેલ લક્ષ્યની સમાન હોય છે.

ઉદાહરણસંયોજનનો સરવાળો લીટકોડ સોલ્યુશન

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 આઉટપુટનો સરવાળો.

સંયોજન સમ લીટકોડ સોલ્યુશન માટે અભિગમ

સમસ્યા માટેનો અભિગમ શોધવા માટે સરળ છે. સામાન્ય રીતે, આ જેવી સમસ્યાઓમાં, આપણે બેકટ્રેકીંગનો ઉપયોગ કરવો જરૂરી છે. કારણ કે આવા પ્રશ્નોમાં અમારે સંપૂર્ણ શોધ કરવી પડશે અને જવાબ શોધવા જોઈએ. તેથી પ્રથમ, આપણે પૂર્ણાંકોની સૂચિ સ sortર્ટ કરીએ છીએ જે આપણને આપવામાં આવે છે. તે પછી, અમે એક રિકરિવ ફંક્શન બનાવીએ છીએ જે વર્તમાન પૂર્ણાંકોની અસ્થાયી સૂચિમાં પૂર્ણાંક ઉમેરવાનું અને આપેલ લક્ષ્યમાં ઉમેરવા માટે બાકીની રકમનો ટ્ર trackક રાખવાનું ચાલુ રાખે છે. તેથી રિકરિવ ફંક્શનની અંદર, આપણે બે બેઝ કેસ રાખીશું. પ્રથમ આધાર કેસ એ જરૂરી છે કે બાકીની રકમ નકારાત્મક જાય છે કે કેમ તે તપાસવાનું છે. તે સ્થિતિમાં, અમે રિકર્સીવ ફંક્શનથી પાછા આવીશું. બીજો આધાર કેસ એ અમારી આવશ્યક સ્થિતિ છે જો બાકી રકમ શૂન્ય બરાબર હોય. જો બાકીની રકમ શૂન્ય હોય તો આનો અર્થ એ કે અમે અમારા આવશ્યક લક્ષ્ય પર પહોંચી ગયા છે. તે બિંદુએ, આપણે પૂર્ણાંકોની વર્તમાન અસ્થાયી સૂચિને એરેના આઉટપુટ એરેમાં દબાણ કરીએ છીએ.

કોડ

કોમ્બિનેશન સમ લીટકોડ સોલ્યુશન માટે સી ++ કોડ

#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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન ^ (એમ / ટી + 1)) જ્યાં એન ઉમેદવારોની સંખ્યા છે, બધા આપેલ પૂર્ણાંકોમાં એમ સૌથી નાનો ઉમેદવાર છે, અને ટી લક્ષ્ય મૂલ્ય છે. આમ સમય જટિલતા ઘાતાંકીય છે અને આ અપેક્ષિત છે કારણ કે અલ્ગોરિધમનો રિકર્સિવ બેકટ્રેકિંગ છે.

અવકાશ જટિલતા

ઓ (ટી / એમ), જ્યાં ટી લક્ષ્ય મૂલ્ય છે અને અન્ય તમામ ઉમેદવારોમાં એમ ન્યૂનતમ તત્વ છે.